QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#866768#8811. Heat Strokelgvc#6 40ms265088kbC++231.7kb2025-01-22 18:26:022025-01-22 18:26:02

Judging History

This is the latest submission verdict.

  • [2025-01-22 18:26:02]
  • Judged
  • Verdict: 6
  • Time: 40ms
  • Memory: 265088kb
  • [2025-01-22 18:26:02]
  • 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++) {
		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);
}

详细

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%