QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #866822 | #8811. Heat Stroke | lgvc | 0 | 59ms | 1348552kb | C++23 | 3.0kb | 2025-01-22 19:40:56 | 2025-01-22 19:40:56 |
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[70000009][2],v2[70000009][2],
su[8009],ff[8009][8009],su2[8009];
std::vector<int> t[8009];
int sv2(int n,int x,int y,int op);
int sv(int n,int x,int y,int op);
int fd(int n,int x,int y,int op) {
int a=sv(n,x,y,op);
if((n==N-1)||(x==c[n])) return a;
int l1=0;
if(x<c[n]) l1=t[n][x+1]-1;else l1=L;
a=std::min(a,sv2(n,ff[n+1][l1],((op==0)?(y):(x-y)),op)+x);
return a;
}
int sv2(int n,int x,int y,int op) {
if(x<0) return INF;
int id=x*(c[n]+1)+y+su2[n-1];
if(v2[id][op]!=-1) return v2[id][op];
int ans=sv2(n,x-1,y,op);
for(int xx=x;xx<=x;xx++) {
int l2=0,l1=0;
if(x<c[n]) l1=t[n][x+1]-1;else l1=L;
if(xx<c[n+1]) l2=t[n+1][xx+1]-1;else l2=L;
//if(l2>l1) continue;
int lim=l2;
int tp1=la[lim][n],tp2=la[lim][n+1];
int vv=va[n+1];
if(op==1) vv-=std::min(y,tp1);
else vv-=(std::max(tp1,y)-y);
if(vv<=0) {
ans=std::min(ans,fd(n+1,xx,0,0));
} else {
int yy=vv;
if(yy<=tp2) ans=std::min(ans,fd(n+1,xx,yy,0));
yy=vv+xx-std::min(xx,tp2);
if(yy<=xx) ans=std::min(ans,fd(n+1,xx,yy,1));
}
}
return v2[id][op]=ans;
}
int sv(int n,int x,int y,int op) {
int id=x*(c[n]+1)+y+su[n-1];
if(n==N-1) {
if(x<c[n]&&(x-y)<va[n+1]) return INF;
return x;
}
if(vc[id][op]!=-1) {
return vc[id][op];
}
int ans=INF;
int limm=0;
if(x<c[n]) limm=std::max(c[n+1]-1,0);
for(int xx=limm;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];
int vv=va[n+1];
if(op==1) vv-=std::min(x-y,tp1);
else vv-=(std::max(std::min(x,tp1),y)-y);
if((vv<=0)||(xx==c[n+1]&&x==c[n])) {
ans=std::min(ans,fd(n+1,xx,0,0)+x);
} else {
int yy=vv;
if(yy<=tp2) ans=std::min(ans,fd(n+1,xx,yy,0)+x);
yy=vv+xx-std::min(xx,tp2);
if(yy<=xx) ans=std::min(ans,fd(n+1,xx,yy,1)+x);
}
}
return vc[id][op]=ans;
}
signed main(void) {
memset(vc,-1,sizeof(vc));
memset(v2,-1,sizeof(v2));
scanf("%d",&N);
for(int i=1;i<=N;i++) {
scanf("%d",&va[i]);
t[i].push_back(0);
}
scanf("%d",&L);
for(int i=1;i<=L;i++) {
int x;
scanf("%d",&x);
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;
}
for(int i=1;i<=N;i++) {
int la=0;
for(int j=0;j<=c[i];j++) {
int l2=0;
if(j<c[i]) l2=t[i][j+1]-1;else l2=L+1;
for(int k=la;k<l2;k++) {
ff[i][k]=j-1;
}
la=l2;
}
}
for(int i=1;i<=N;i++) {
su[i]=su[i-1]+(c[i]+1)*(c[i]+1);
su2[i]=su2[i-1]+(c[i]+1)*c[i+1];
assert(su2[i]<=70000000);
}
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,fd(1,i,j,0));
if((i==c[1])||(j==va[1])) ans=std::min(ans,fd(1,i,j,1));
}
}
// printf("%d\n",sv(4,0,0,0));
printf("%d",L-ans);
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 6
Accepted
time: 43ms
memory: 1099464kb
input:
2 0 0 1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 6
Accepted
time: 42ms
memory: 1099588kb
input:
2 0 1 1 1
output:
0
result:
ok single line: '0'
Test #3:
score: 6
Accepted
time: 37ms
memory: 1099592kb
input:
2 1 0 1 1
output:
0
result:
ok single line: '0'
Test #4:
score: 6
Accepted
time: 50ms
memory: 1101640kb
input:
2 1 1 1 1
output:
0
result:
ok single line: '0'
Test #5:
score: 6
Accepted
time: 41ms
memory: 1099596kb
input:
2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #6:
score: 6
Accepted
time: 37ms
memory: 1099592kb
input:
2 1 1 2 1 1
output:
0
result:
ok single line: '0'
Test #7:
score: 6
Accepted
time: 38ms
memory: 1099592kb
input:
2 2 2 2 1 1
output:
0
result:
ok single line: '0'
Test #8:
score: 6
Accepted
time: 33ms
memory: 1099596kb
input:
2 3 3 2 1 1
output:
0
result:
ok single line: '0'
Test #9:
score: 6
Accepted
time: 44ms
memory: 1101764kb
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: 43ms
memory: 1113544kb
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: 57ms
memory: 1131464kb
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: 41ms
memory: 1131592kb
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: 44ms
memory: 1131464kb
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: 29ms
memory: 1099592kb
input:
3 0 1 1 2 1 2
output:
0
result:
ok single line: '0'
Test #15:
score: 6
Accepted
time: 38ms
memory: 1099592kb
input:
3 1 1 1 3 1 2 2
output:
1
result:
ok single line: '1'
Test #16:
score: 6
Accepted
time: 40ms
memory: 1099592kb
input:
3 1 2 0 3 1 1 2
output:
1
result:
ok single line: '1'
Test #17:
score: 6
Accepted
time: 43ms
memory: 1099592kb
input:
3 1 2 0 3 1 2 2
output:
1
result:
ok single line: '1'
Test #18:
score: 6
Accepted
time: 33ms
memory: 1099596kb
input:
3 1 3 0 4 1 1 1 2
output:
1
result:
ok single line: '1'
Test #19:
score: 6
Accepted
time: 43ms
memory: 1099596kb
input:
4 0 2 1 1 4 1 1 2 3
output:
0
result:
ok single line: '0'
Test #20:
score: 6
Accepted
time: 39ms
memory: 1099556kb
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: 0
Wrong Answer
time: 59ms
memory: 1348552kb
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:
834
result:
wrong answer 1st lines differ - expected: '843', found: '834'
Subtask #2:
score: 0
Wrong Answer
Test #33:
score: 7
Accepted
time: 32ms
memory: 1099592kb
input:
3 1 1 1 3 1 2 1
output:
1
result:
ok single line: '1'
Test #34:
score: 7
Accepted
time: 39ms
memory: 1099588kb
input:
3 1 1 1 3 2 1 2
output:
1
result:
ok single line: '1'
Test #35:
score: 7
Accepted
time: 36ms
memory: 1099596kb
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: 37ms
memory: 1099588kb
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: 7
Accepted
time: 43ms
memory: 1099716kb
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:
1
result:
ok single line: '1'
Test #38:
score: 7
Accepted
time: 32ms
memory: 1099592kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 15 17 12 6 3 15 17 3 10 6 12 15 17 11 12 14
output:
3
result:
ok single line: '3'
Test #39:
score: 7
Accepted
time: 39ms
memory: 1099592kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 16 11 13 10 5 3 10 6 13 16 16 2 14 9 9 3
output:
4
result:
ok single line: '4'
Test #40:
score: 7
Accepted
time: 38ms
memory: 1099468kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 17 12 5 4 1 10 6 8 8 16 6 12 14 7 14 17 12 9
output:
4
result:
ok single line: '4'
Test #41:
score: 0
Wrong Answer
time: 40ms
memory: 1099464kb
input:
18 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 18 14 9 3 16 9 2 2 9 4 10 12 17 13 10 10 10 3 11
output:
6
result:
wrong answer 1st lines differ - expected: '7', found: '6'
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%