QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#882126 | #8811. Heat Stroke | Matutino | 0 | 24ms | 9120kb | C++17 | 2.3kb | 2025-02-04 21:17:35 | 2025-02-04 21:17:40 |
Judging History
answer
#include<bits/stdc++.h>
#define reg register
// #define int long long
inline int read(){
reg int x=0,k=1; reg char ch=getchar();
while (ch<'0'||ch>'9') (ch=='-')&&(k=-1),ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*k;
}
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=110;
int n,L,C[N],f[N][N][N];
std::vector<int> vc[N];
signed main(){
L=read(); for (reg int i=1;i<=L;i++) C[i]=read();
n=read(); for (reg int i=1;i<=n;i++) vc[read()].push_back(i);
memset(f,-0x3f,sizeof(f));
// reg int now=0;
for (reg int i=0;i<=n+1;i++) f[0][0][i]=0;
for (reg int i=1;i<L;i++){
// now^=1;
for (reg int j=0;j<=C[i]&&j<=vc[i-1].size();j++) for (reg int k=0;k<=n;k++)if (f[i-1][j][k]>=0){
if (C[i]-j>vc[i].size()) continue;
if (C[i]-j&&vc[i][C[i]-j-1]>k) continue;
reg int pos=std::upper_bound(vc[i].begin(),vc[i].end(),k)-vc[i].begin()-1;
for (reg int y=0,p=-1;y<=n+1;y++){
while (p+1<vc[i].size()&&vc[i][p+1]<=y) p++;
// std::cerr<<"<< "<<y<<" "<<p<<"\n";
if (p<=pos-C[i]+j){
// if (vc[i].size()-1-p-(C[i]-j)==2) std::cerr<<"qwq\n";
cmax(f[i][pos-C[i]+j-p][y],f[i-1][j][k]+vc[i].size()-1-pos);
}
else if (p>pos) cmax(f[i][p+1-(C[i]-j)][y],f[i-1][j][k]+vc[i].size()-1-p);
else cmax(f[i][pos+1-C[i]+j][y],f[i-1][j][k]+vc[i].size()-1-pos);
}
cmax(f[i][0][n+1],f[i-1][j][k]);
}
for (reg int j=0;j<=C[i];j++){
for (reg int x=0;x<=vc[i].size()&&x<=C[i+1];x++)
for (reg int y=x?vc[i][x-1]:0;y<=n+1;y++) cmax(f[i][x][y],f[i-1][j][n+1]);
}
// for (reg int j=0;j<=C[i]&&j<=vc[i-1].size();j++) memset(f[now^1][j],-0x3f,n+2<<2);
}
reg int ans=0;
for (reg int i=0;i<=n;i++){
cmax(ans,f[L-1][C[L]][i]);
// if (f[L-1][C[n]][i]==1) std::cerr<<"<< "<<i<<"\n";
}
for (reg int i=0;i<=C[L];i++){
cmax(ans,f[L-1][i][n+1]);
// if (f[L-1][i][n+1]==1) std::cerr<<"<< "<<i<<"\n";
}
// std::cerr<<"<< "<<f[1][0][5]<<"\n";
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 0ms
memory: 9020kb
input:
2 0 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 6
Accepted
time: 0ms
memory: 8864kb
input:
2 0 1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 0ms
memory: 8932kb
input:
2 1 0 1 1
output:
0
result:
ok single line: '0'
Test #4:
score: 6
Accepted
time: 1ms
memory: 9100kb
input:
2 1 1 1 1
output:
0
result:
ok single line: '0'
Test #5:
score: 6
Accepted
time: 0ms
memory: 8852kb
input:
2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #6:
score: 6
Accepted
time: 2ms
memory: 9120kb
input:
2 1 1 2 1 1
output:
0
result:
ok single line: '0'
Test #7:
score: 6
Accepted
time: 0ms
memory: 8940kb
input:
2 2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #8:
score: 6
Accepted
time: 1ms
memory: 8908kb
input:
2 3 3 2 1 1
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Wrong Answer
time: 24ms
memory: 8872kb
input:
2 298 299 600 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
302
result:
wrong answer 1st lines differ - expected: '3', found: '302'
Subtask #2:
score: 0
Wrong Answer
Test #33:
score: 7
Accepted
time: 0ms
memory: 9076kb
input:
3 1 1 1 3 1 2 1
output:
1
result:
ok single line: '1'
Test #34:
score: 7
Accepted
time: 0ms
memory: 9060kb
input:
3 1 1 1 3 2 1 2
output:
1
result:
ok single line: '1'
Test #35:
score: 7
Accepted
time: 0ms
memory: 9120kb
input:
7 1 1 1 1 1 1 1 8 2 1 6 5 4 3 2 6
output:
3
result:
ok single line: '3'
Test #36:
score: 7
Accepted
time: 0ms
memory: 8940kb
input:
8 1 1 1 1 1 1 1 1 10 6 7 4 1 2 3 4 5 6 1
output:
4
result:
ok single line: '4'
Test #37:
score: 0
Wrong Answer
time: 1ms
memory: 9060kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 13 13 17 13 9 15 4 12 11 12 7 5 15 1
output:
2
result:
wrong answer 1st lines differ - expected: '1', found: '2'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #1:
0%