QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #307162 | #2500. Collecting Stamps 3 | OAleksa | 0 | 1ms | 3728kb | C++14 | 2.4kb | 2024-01-18 06:16:38 | 2024-01-18 06:16:38 |
answer
#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 210;
const int inf = 1e18;
int n, l, x[N], t[N], dp[N][N][2][2];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> l;
for (int i = 1;i <= n;i++) {
cin >> x[i];
}
for (int i = 1;i <= n;i++) {
cin >> t[i];
}
x[n + 1] = l;
for (int i = 0;i <= n;i++) {
for (int j = 0;j <= n;j++)
dp[i][j][0][0] = dp[i][j][1][0] = inf;
}
//3-i/j
//4-time/skor
dp[0][0][0][0] = dp[0][0][1][0] = 0;
int ans = 0;
for (int i = 0;i <= n;i++) {
for (int j = 0;j <= n;j++) {
// if (i + j > n)
// break;
for (int k = i - 1;k >= 0;k--) {
int time = dp[k][j][0][0] + abs(x[i] - x[k]);
if (dp[i][j][0][1] < dp[k][j][0][1] + (time <= t[i])) {
dp[i][j][0][1] = dp[k][j][0][1] + (time <= t[i]);
dp[i][j][0][0] = time;
}
else if (dp[i][j][0][1] == dp[k][j][0][1] + (time <= t[i]))
dp[i][j][0][0] = min(dp[i][j][0][0], time);
time = dp[k][j][1][0] + x[i] + (l - x[n - j + 1]);
if (dp[i][j][0][1] < dp[k][j][1][1] + (time <= t[i])) {
dp[i][j][0][1] = dp[k][j][1][1] + (time <= t[i]);
dp[i][j][0][0] = time;
}
else if (dp[i][j][0][1] == dp[k][j][1][1] + (time <= t[i]))
dp[i][j][0][0] = min(dp[i][j][0][0], time);
}
for (int k = j - 1;k >= 0;k--) {
int time = dp[i][k][1][0] + abs(x[n - j + 1] - x[n - k + 1]);
if (dp[i][j][1][1] < dp[i][k][1][1] + (time <= t[n - j + 1])) {
dp[i][j][1][1] = dp[i][k][1][1] + (time <= t[n - j + 1]);
dp[i][j][1][0] = time;
}
else if (dp[i][j][1][1] == dp[i][k][1][1] + (time <= t[n - j + 1]))
dp[i][j][1][0] = min(dp[i][j][1][0], time);
time = dp[i][k][0][0] + x[i] + (l - x[n - j + 1]);
if (dp[i][j][1][1] < dp[i][k][0][1] + (time <= t[n - j + 1])) {
dp[i][j][1][1] = dp[i][k][0][1] + (time <= t[n - j + 1]);
dp[i][j][1][0] = time;
}
else if (dp[i][j][1][1] == dp[i][k][0][1] + (time <= t[n - j + 1]))
dp[i][j][1][0] = min(dp[i][j][1][0], time);
}
ans = max(ans, max(dp[i][j][0][1], dp[i][j][1][1]));
}
}
cout << ans;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3508kb
input:
5 180 137 149 164 167 171 18 76 14 55 116
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
5 198 5 12 18 190 192 16 43 200 33 0
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
9 198 3 17 22 33 43 44 48 54 65 0 17 29 32 38 46 45 54 66
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6 171 22 30 46 85 96 149 18 179 19 69 87 96
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
7 198 5 8 14 188 191 194 197 7 18 50 69 80 35 8
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
12 198 71 72 83 94 108 112 119 140 142 143 166 174 124 119 124 111 91 94 85 48 60 63 40 32
output:
9
result:
ok single line: '9'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8 178 32 55 69 99 115 134 152 156 61 109 37 65 76 31 103 0
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
10 198 1 2 3 10 14 182 183 190 192 196 0 3 17 46 115 142 79 44 8 1
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
12 198 18 23 45 53 54 70 101 103 105 110 118 152 21 24 49 45 61 78 108 111 97 107 122 144
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
1 2 1 0
output:
0
result:
ok single line: '0'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
1 2 1 1
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
12 170 1 4 7 28 32 63 84 85 90 94 96 107 116 77 30 93 134 99 190 103 96 189 173 191
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
12 200 14 25 35 57 113 120 141 143 146 153 173 179 126 137 127 141 135 134 122 100 164 185 163 188
output:
9
result:
ok single line: '9'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
7 171 4 31 65 82 125 128 150 1 24 51 55 8 23 18
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
8 175 28 41 67 77 89 104 106 138 16 9 0 56 25 39 42 14
output:
0
result:
ok single line: '0'
Test #16:
score: -5
Wrong Answer
time: 0ms
memory: 3664kb
input:
12 13 1 2 3 4 5 6 7 8 9 10 11 12 0 200 200 200 200 200 200 200 200 200 200 200
output:
22
result:
wrong answer 1st lines differ - expected: '11', found: '22'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%