QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #479963 | #8811. Heat Stroke | real_sigma_team# | 0 | 1ms | 7856kb | C++20 | 3.1kb | 2024-07-15 23:35:40 | 2024-07-15 23:35:41 |
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';
}
Details
Tip: Click on the bar to expand more detailed information
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%