QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#866768 | #8811. Heat Stroke | lgvc# | 6 | 40ms | 265088kb | C++23 | 1.7kb | 2025-01-22 18:26:02 | 2025-01-22 18:26:02 |
Judging History
answer
#include <bits/stdc++.h>
//0 qian j ge
//1 hou j ge
#define INF 0x3f3f3f3f
int N,L,va[8009],c[8009],la[8009][8009],vc[109][109][109][2];
std::vector<int> t[8009];
int sv(int n,int x,int y,int op) {
if(vc[n][x][y][op]!=-1) {
return vc[n][x][y][op];
}
if(n==N-1) {
if(x<c[n]&&(x-y)<va[n+1]) return INF;
return x;
}
int ans=INF;
for(int xx=0;xx<=c[n+1];xx++) {
int l1=0,l2=0;
if(xx<c[n+1]) l2=t[n+1][xx+1]-1;else l2=L;
if(x<c[n]) l1=t[n][x+1]-1;else l1=L;
int lim=std::min(l1,l2);
int tp1=la[lim][n],tp2=la[lim][n+1];
for(int yy=0;yy<=xx;yy++) {
int vv=va[n+1];
if(op==1) vv-=std::min(x-y,tp1);
else vv-=(std::max(std::min(x,tp1),y)-y);
int vt=vv-std::min(yy,tp2);
if((vt>=0)&&((xx==c[n+1]&&x==c[n])||(vt==0))) {
ans=std::min(ans,sv(n+1,xx,yy,0)+x);
}
vt=vv;
vt-=std::max(std::min(xx,tp2),xx-yy)-(xx-yy);
if((vt>=0)&&((xx==c[n+1]&&x==c[n])||(vt==0))) {
ans=std::min(ans,sv(n+1,xx,yy,1)+x);
}
}
}
return vc[n][x][y][op]=ans;
}
signed main(void) {
memset(vc,-1,sizeof(vc));
scanf("%d",&N);
for(int i=1;i<=N;i++) {
scanf("%d",&va[i]);
t[i].push_back(0);
}
scanf("%d",&L);
int anss=0;
for(int i=1;i<=L;i++) {
int x;
scanf("%d",&x);
if(va[x+1]) {
va[x+1]--;
} else if(va[x]) {
va[x]--;
} else {
anss++;
}
t[x].push_back(i);
c[x]++;
for(int j=1;j<=N;j++) {
la[i][j]=la[i-1][j];
}
la[i][x]=t[x].size()-1;
}
printf("%d",anss);
return 0;
int ans=0x3f3f3f3f;
for(int i=0;i<=c[1];i++) {
for(int j=0;j<=i&&j<=va[1];j++) {
if((i==c[1])||(j==va[1])) ans=std::min(ans,sv(1,i,j,0));
if((i==c[1])||(j==va[1])) ans=std::min(ans,sv(1,i,j,1));
}
}
// printf("%d\n",sv(4,0,0,0));
printf("%d",L-ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 6
Accepted
Test #1:
score: 6
Accepted
time: 0ms
memory: 14540kb
input:
2 0 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 6
Accepted
time: 0ms
memory: 15684kb
input:
2 0 1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 0ms
memory: 15336kb
input:
2 1 0 1 1
output:
0
result:
ok single line: '0'
Test #4:
score: 6
Accepted
time: 0ms
memory: 15040kb
input:
2 1 1 1 1
output:
0
result:
ok single line: '0'
Test #5:
score: 6
Accepted
time: 0ms
memory: 15604kb
input:
2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #6:
score: 6
Accepted
time: 2ms
memory: 14152kb
input:
2 1 1 2 1 1
output:
0
result:
ok single line: '0'
Test #7:
score: 6
Accepted
time: 1ms
memory: 14500kb
input:
2 2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #8:
score: 6
Accepted
time: 0ms
memory: 15212kb
input:
2 3 3 2 1 1
output:
0
result:
ok single line: '0'
Test #9:
score: 6
Accepted
time: 0ms
memory: 34080kb
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:
3
result:
ok single line: '3'
Test #10:
score: 6
Accepted
time: 1ms
memory: 50276kb
input:
2 1749 1749 3500 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:
2
result:
ok single line: '2'
Test #11:
score: 6
Accepted
time: 1ms
memory: 76656kb
input:
2 3999 3999 8000 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:
2
result:
ok single line: '2'
Test #12:
score: 6
Accepted
time: 2ms
memory: 76520kb
input:
2 1 1 8000 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 1 1...
output:
7998
result:
ok single line: '7998'
Test #13:
score: 6
Accepted
time: 1ms
memory: 67784kb
input:
2 0 0 8000 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 1 1...
output:
8000
result:
ok single line: '8000'
Test #14:
score: 6
Accepted
time: 0ms
memory: 14536kb
input:
3 0 1 1 2 1 2
output:
0
result:
ok single line: '0'
Test #15:
score: 6
Accepted
time: 0ms
memory: 14244kb
input:
3 1 1 1 3 1 2 2
output:
1
result:
ok single line: '1'
Test #16:
score: 6
Accepted
time: 0ms
memory: 14632kb
input:
3 1 2 0 3 1 1 2
output:
1
result:
ok single line: '1'
Test #17:
score: 6
Accepted
time: 0ms
memory: 16200kb
input:
3 1 2 0 3 1 2 2
output:
1
result:
ok single line: '1'
Test #18:
score: 6
Accepted
time: 0ms
memory: 15184kb
input:
3 1 3 0 4 1 1 1 2
output:
1
result:
ok single line: '1'
Test #19:
score: 6
Accepted
time: 0ms
memory: 15276kb
input:
4 0 2 1 1 4 1 1 2 3
output:
0
result:
ok single line: '0'
Test #20:
score: 6
Accepted
time: 0ms
memory: 16788kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 33 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17
output:
15
result:
ok single line: '15'
Test #21:
score: 6
Accepted
time: 19ms
memory: 122564kb
input:
8000 0 2 0 0 0 0 0 0 1 0 0 2 1 1 0 1 1 0 2 2 0 0 0 1 1 0 0 0 0 1 1 1 2 3 0 2 2 0 0 1 0 1 2 1 1 0 1 1 0 0 0 0 1 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 2 0 0 0 0 0 1 0 1 1 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 2 2 0 3 2 0 0 0 0 0 1 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 3 0...
output:
843
result:
ok single line: '843'
Test #22:
score: 6
Accepted
time: 35ms
memory: 264856kb
input:
8000 1 0 1 2 3 2 1 1 1 1 2 4 1 3 2 2 0 3 2 0 1 1 1 1 0 0 0 0 1 0 4 4 3 0 0 0 2 1 0 0 0 0 0 0 0 0 0 2 0 3 3 0 2 0 0 0 2 0 0 2 2 0 1 5 3 0 0 3 0 1 1 2 1 1 2 2 0 0 3 0 0 1 0 0 1 0 1 1 2 3 0 0 1 4 1 2 1 1 2 1 0 0 0 2 2 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 0 3 0 1 1 0 1 1 1 0 0 2 1 1 3 3 0 1 0 0 4 1 0 0 1 0 0...
output:
1799
result:
ok single line: '1799'
Test #23:
score: 6
Accepted
time: 39ms
memory: 264824kb
input:
8000 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 1 1 1 1 1...
output:
2146
result:
ok single line: '2146'
Test #24:
score: 6
Accepted
time: 40ms
memory: 265088kb
input:
8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 8000 ...
output:
0
result:
ok single line: '0'
Test #25:
score: 6
Accepted
time: 20ms
memory: 170300kb
input:
3579 0 3 5 0 3 0 1 6 5 1 1 7 0 1 2 0 0 4 3 1 0 4 2 8 2 5 2 2 3 2 0 0 1 4 2 2 2 4 2 0 4 1 0 4 0 5 3 4 1 8 6 0 0 0 2 4 1 2 7 8 2 2 3 5 0 1 0 0 2 1 4 6 4 4 1 1 4 2 1 0 3 3 0 4 4 1 1 6 0 1 2 0 0 1 3 7 3 2 1 3 2 2 1 0 0 0 1 5 4 4 3 0 3 4 4 3 2 1 2 2 1 1 2 1 1 3 11 1 2 0 3 0 4 1 3 3 6 2 1 7 6 2 0 1 3 0 1 ...
output:
1634
result:
ok single line: '1634'
Test #26:
score: 6
Accepted
time: 9ms
memory: 101104kb
input:
1357 11 16 5 0 6 10 10 7 5 1 12 13 4 9 4 6 0 6 1 11 2 8 7 8 1 4 8 9 3 3 3 4 1 4 4 1 5 6 18 7 10 6 9 7 10 2 10 6 1 2 4 12 9 5 7 5 4 5 1 4 4 6 1 4 11 3 13 3 12 7 0 3 9 1 5 6 3 2 3 0 13 2 8 1 6 10 4 5 15 1 1 1 2 5 7 8 5 11 3 7 4 2 0 7 3 6 6 0 3 1 5 4 13 13 5 5 0 6 1 7 9 1 8 1 6 8 12 2 2 2 5 8 11 5 7 6 ...
output:
1608
result:
ok single line: '1608'
Test #27:
score: 6
Accepted
time: 3ms
memory: 70468kb
input:
68 38 219 171 204 116 205 90 225 221 43 74 153 142 147 151 133 65 189 196 4 91 93 215 80 213 25 180 16 24 143 60 22 129 190 59 70 242 53 205 95 212 26 69 123 50 47 205 5 62 154 78 203 48 99 118 7 25 151 222 141 151 143 90 90 141 228 193 75 8000 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:
1018
result:
ok single line: '1018'
Test #28:
score: 6
Accepted
time: 2ms
memory: 62556kb
input:
3 137 4887 1630 8000 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:
1483
result:
ok single line: '1483'
Test #29:
score: 6
Accepted
time: 1ms
memory: 62688kb
input:
3 1 7999 0 8000 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:
1
result:
ok single line: '1'
Test #30:
score: 6
Accepted
time: 0ms
memory: 18592kb
input:
4 0 50 50 0 100 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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
output:
0
result:
ok single line: '0'
Test #31:
score: 6
Accepted
time: 2ms
memory: 68756kb
input:
4 0 4000 4000 0 8000 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:
0
result:
ok single line: '0'
Test #32:
score: 6
Accepted
time: 8ms
memory: 91684kb
input:
800 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 2 0 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 3 0 3 1 3 2 3 3 3 4 3 5 3 ...
output:
1330
result:
ok single line: '1330'
Subtask #2:
score: 0
Wrong Answer
Test #33:
score: 0
Wrong Answer
time: 0ms
memory: 14172kb
input:
3 1 1 1 3 1 2 1
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
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:
100%
Accepted
Dependency #2:
0%