QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#866754#8811. Heat Strokelgvc#0 1ms15256kbC++231.7kb2025-01-22 18:17:482025-01-22 18:17:49

Judging History

This is the latest submission verdict.

  • [2025-01-22 18:17:49]
  • Judged
  • Verdict: 0
  • Time: 1ms
  • Memory: 15256kb
  • [2025-01-22 18:17:48]
  • Submitted

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++) {
		for(int yy=0;yy<=xx;yy++) {
			int tp;
			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);
///			if(n==4) printf("%d %d %d %d %d\n",xx,yy,lim,l1,l2);
			int vv=va[n+1];
			int tp1=la[lim][n],tp2=la[lim][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);
	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;
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=c[1];i++) {
		for(int j=0;j<=c[1]&&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: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 14720kb

input:

2
0 0
1
1

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Subtask #2:

score: 0
Wrong Answer

Test #33:

score: 7
Accepted
time: 0ms
memory: 14908kb

input:

3
1 1 1
3
1 2 1

output:

1

result:

ok single line: '1'

Test #34:

score: 7
Accepted
time: 0ms
memory: 14168kb

input:

3
1 1 1
3
2 1 2

output:

1

result:

ok single line: '1'

Test #35:

score: 7
Accepted
time: 0ms
memory: 15124kb

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: 15060kb

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: 0ms
memory: 15256kb

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: 0
Wrong Answer
time: 0ms
memory: 14904kb

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:

-1061109552

result:

wrong answer 1st lines differ - expected: '3', found: '-1061109552'

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%