QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#479963#8811. Heat Strokereal_sigma_team#0 1ms7856kbC++203.1kb2024-07-15 23:35:402024-07-15 23:35:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 23:35:41]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:7856kb
  • [2024-07-15 23:35:40]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve();

int main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif
	cout << fixed << setprecision(30);
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
}

constexpr int N = 8080;
int c[N], a[N], ans[N][N], anst[N][N], dp[N];
vector<int> cnt[N], lft[N], rgt[N], lfts[N], rgts[N];

void solve() {
	int l;
	cin >> l;
	c[0] = N;
	c[l + 1] = N;
	for (int i = 1; i <= l; i++) {
		cin >> c[i];
	}
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		cnt[a[i]].push_back(i);
	}
	for (int i = 0; i <= l; i++) {
		for (int j = 0; j <= l + 1; j++) {
			lft[j].clear();
			rgt[j].clear();
		}
		ans[i][i + 1] = 0;
		anst[i][i + 1] = 0;
		for (int k : cnt[i]) {
			if (rgt[i].size() < c[i + 1]) {
				rgt[i].push_back(k);
			} else {
				lft[i].push_back(k);
			}
		}
		for (int j = i + 2; j <= l + 1; j++) {
			ans[i][j] = anst[i][j - 1];
			anst[i][j] = anst[i][j - 1];
			for (int j = 0; j <= l + 1; j++) {
				lfts[j] = lft[j];
				rgts[j] = rgt[j];
			}
			for (int k : cnt[j - 1]) {
				if (rgt[j - 2].size() + lft[j - 1].size() < c[j - 1]) {
					lft[j - 1].push_back(k);
				} else if (!rgt[j - 2].empty() && rgt[j - 2].back() > k) {
					lft[j - 1].push_back(k);
					int nw = rgt[j - 2].back(), nwi = j - 2;
					rgt[j - 2].pop_back();
					while (nwi > i && !rgt[nwi - 1].empty() && rgt[nwi - 1].back() > nw) {
						if (rgt[nwi - 1].size() + lft[nwi].size() < c[nwi]) {
							lft[nwi].push_back(nw);
							nwi = i;
							break;
						}
						lft[nwi].push_back(nw);
						nw = rgt[nwi - 1].back();
						rgt[nwi - 1].pop_back();
						nwi--;
					}
					if (nwi != i && rgt[nwi - 1].size() + lft[nwi].size() < c[nwi]) {
						lft[nwi].push_back(nw);
					} else if (nwi != i) {
						ans[i][j]++;
					}
				}
			}
			for (int j = 0; j <= l + 1; j++) {
				lft[j] = lfts[j];
				rgt[j] = rgts[j];
			}
			int rem = (int)cnt[j - 1].size() - 1;
			for (int k : cnt[j - 1]) {
				if (rgt[j - 2].size() + lft[j - 1].size() < c[j - 1]) {
					lft[j - 1].push_back(k);
				} else if (rgt[j - 1].size() < c[j]) {
					rgt[j - 1].push_back(k);
				} else if (!rgt[j - 2].empty() && rgt[j - 2].back() > k) {
					lft[j - 1].push_back(k);
					int nw = rgt[j - 2].back(), nwi = j - 2;
					rgt[j - 2].pop_back();
					while (nwi > i && !rgt[nwi - 1].empty() && rgt[nwi - 1].back() > nw) {
						if (rgt[nwi - 1].size() + lft[nwi].size() < c[nwi]) {
							lft[nwi].push_back(nw);
							nwi = i;
							break;
						}
						lft[nwi].push_back(nw);
						nw = rgt[nwi - 1].back();
						rgt[nwi - 1].pop_back();
						nwi--;
					}
					if (nwi != i && rgt[nwi - 1].size() + lft[nwi].size() < c[nwi]) {
						lft[nwi].push_back(nw);
					} else if (nwi != i) {
						anst[i][j]++;
					}
				} else {
					anst[i][j]++;
				}
				rem--;
			}
		}
	}
	dp[0] = 0;
	dp[1] = 0;
	for (int i = 2; i <= l + 1; i++) {
		dp[i] = 0;
		for (int j = i - 1; j >= 0; j--) {
			dp[i] = max(dp[i], dp[j] + ans[j][i]);
		}
	}
	cout << dp[l + 1] << '\n';
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 6
Accepted
time: 1ms
memory: 5796kb

input:

2
0 0
1
1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5720kb

input:

2
0 1
1
1

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7764kb

input:

2
1 0
1
1

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 7752kb

input:

2
1 1
1
1

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 1ms
memory: 7636kb

input:

2
2 2
1
1

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 5732kb

input:

2
1 1
2
1 1

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 1ms
memory: 7736kb

input:

2
2 2
2
1 1

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 1ms
memory: 5728kb

input:

2
3 3
2
1 1

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 1ms
memory: 5712kb

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: 0
Accepted
time: 1ms
memory: 7840kb

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: 0
Accepted
time: 1ms
memory: 7856kb

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: 0
Accepted
time: 0ms
memory: 5892kb

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: 0
Accepted
time: 1ms
memory: 5808kb

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: 0
Accepted
time: 1ms
memory: 5724kb

input:

3
0 1 1
2
1 2

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 1ms
memory: 5652kb

input:

3
1 1 1
3
1 2 2

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 1ms
memory: 7752kb

input:

3
1 2 0
3
1 1 2

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 5804kb

input:

3
1 2 0
3
1 2 2

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 1ms
memory: 5644kb

input:

3
1 3 0
4
1 1 1 2

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 1ms
memory: 5732kb

input:

4
0 2 1 1
4
1 1 2 3

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 5732kb

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
Time Limit Exceeded

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:


result:


Subtask #2:

score: 0
Wrong Answer

Test #33:

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

input:

3
1 1 1
3
1 2 1

output:

1

result:

ok single line: '1'

Test #34:

score: 0
Accepted
time: 1ms
memory: 5708kb

input:

3
1 1 1
3
2 1 2

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 1ms
memory: 5756kb

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
Wrong Answer
time: 1ms
memory: 5760kb

input:

8
1 1 1 1 1 1 1 1
10
6 7 4 1 2 3 4 5 6 1

output:

3

result:

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

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%