QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751904 | #4906. 球球 | NineSuns | 5 | 24ms | 28264kb | C++14 | 2.1kb | 2024-11-15 21:14:42 | 2024-11-15 21:14:49 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define int long long
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5005, inf = 0x3f3f3f3f3f3f3f3f;
int n, g[N], t[N], x[N];
bool f[N][N], h[N];
void solve () {
cin >> n;
for (int i = 1;i <= n;i++) cin >> t[i] >> x[i];
memset(g, 0x3f, sizeof g);
g[0] = 0; h[0] = 1;
for (int i = 0;i <= n;i++) {
if (i) g[i] = min(g[i], max(t[i-1], g[i-1])+llabs(x[i]-x[i-1]));
if (i && x[i] == x[i-1]) g[i] = min(g[i], g[i-1]);
if (g[i] > t[i]) g[i] = inf;
for (int j = 0;j <= n;j++) h[i] |= f[i][j];
if (i < n && h[i]) {
h[i+1] |= (t[i+1]-t[i] >= llabs(x[i+1]-x[i]));
for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-t[i] >= llabs(x[j]-x[i])+llabs(x[i+1]-x[j]);
}
if (i && f[i-1][i] && i < n) {
g[i+1] = min(g[i+1], max(t[i], t[i-1]+llabs(x[i+1]-x[i-1])));
h[i+1] |= t[i+1]-t[i-1] >= llabs(x[i+1]-x[i-1]);
for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-max(t[i], t[i-1]+llabs(x[i-1]-x[j])) >= llabs(x[j]-x[i+1]); //, cout << i << " " << j << " " << "DCHK:" << t[i+1]-t[i-1] << " " << abs(x[i]-x[j]) << " " << abs(x[j]-x[i+1]) << " " << f[i+1][j] << endl;
}
if (g[i] <= t[i] && i < n) {
h[i+1] |= t[i+1]-g[i] >= llabs(x[i+1]-x[i]);
for (int j = i+1;j <= n;j++) f[i+1][j] |= t[i+1]-max(t[i], g[i]+llabs(x[i]-x[j])) >= llabs(x[j]-x[i+1]);
// for (int j = i+1;j <= n;j++) f[i+1][j] |= (t[i+1]-g[i]) >= abs(x[i]-x[j])+abs(x[j]-x[i+1]); //, cout << i << " " << j << " " << "CHK:" << t[i+1]-g[i] << " " << abs(x[i]-x[j]) << " " << abs(x[j]-x[i+1]) << " " << f[i+1][j] << endl;
}
for (int j = 0;j <= n;j++) f[i+1][j] |= f[i][j]&(t[i+1]-t[i] >= llabs(x[i+1]-x[i]));
// for (int j = 0;j <= n;j++) cout << f[i][j] << " "; cout << endl;
// cout << g[i] << endl;
} // cout << endl;
int fl = g[n] <= t[n] || f[n-1][n] || h[n];
puts(fl ? "YES" : "NO");
}
signed main () {
int T = 1;
while (T--) solve();
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3772kb
input:
5 2 1 3 2 9 6 10 5 13 -1
output:
NO
result:
ok single line: 'NO'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3840kb
input:
5 1 1 3 2 4 -1 6 4 10 -1
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 5
Accepted
time: 0ms
memory: 3708kb
input:
4 16 13 18 4 20 3 21 5
output:
NO
result:
ok single line: 'NO'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3708kb
input:
5 2 1 3 2 8 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #5:
score: 5
Accepted
time: 0ms
memory: 3656kb
input:
5 2 1 3 2 9 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #6:
score: 5
Accepted
time: 0ms
memory: 3712kb
input:
5 1 1 3 2 4 0 6 4 10 -1
output:
YES
result:
ok single line: 'YES'
Test #7:
score: 5
Accepted
time: 0ms
memory: 3640kb
input:
3 1 0 5 5 6 2
output:
YES
result:
ok single line: 'YES'
Test #8:
score: 5
Accepted
time: 0ms
memory: 3656kb
input:
5 2 1 6 0 7 -1 8 2 9 -2
output:
YES
result:
ok single line: 'YES'
Test #9:
score: 5
Accepted
time: 0ms
memory: 3652kb
input:
5 30 10 40 -10 51 9 52 8 53 20
output:
YES
result:
ok single line: 'YES'
Test #10:
score: 5
Accepted
time: 0ms
memory: 3768kb
input:
3 2 2 5 5 6 1
output:
YES
result:
ok single line: 'YES'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #11:
score: 5
Accepted
time: 1ms
memory: 6140kb
input:
100 51823 -51823 80072 -23574 152202 48556 263343 -14629 356859 -38607 441850 -193136 442857 -192129 471412 -108145 504392 -187704 582081 -265393 680615 -220684 775219 -261463 781624 -267868 801370 -287614 899570 -166859 982377 -272221 1048767 -338611 1094930 -189414 1170308 -460152 1222829 -512673 ...
output:
YES
result:
ok single line: 'YES'
Test #12:
score: 5
Accepted
time: 1ms
memory: 4040kb
input:
100 106661 51112 155727 44629 204995 -4639 289968 -89612 352826 -26754 358628 -32556 456755 -130683 458435 -4437 484255 -103183 506353 -125281 537685 -93949 599460 -129003 697511 -32174 746550 -179264 749060 -176754 751112 -178806 756783 -173135 847195 -82723 886372 -43546 953837 23919 1050796 -7304...
output:
YES
result:
ok single line: 'YES'
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 5956kb
input:
100 51953 51953 178909 4607 255989 -75003 303522 -152083 375771 -271865 422215 -318309 446399 -294125 534441 -382167 591666 -324942 665189 -398465 759160 -492436 856968 -394628 878236 -415896 978225 -199616 1004339 -342021 1011649 -349331 1056555 -304425 1121330 -315907 1124074 -242394 1192744 -3110...
output:
NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #91:
score: 0
Wrong Answer
time: 24ms
memory: 28264kb
input:
5000 6 6 80 80 170 48 240 106 243 179 329 176 412 93 485 176 552 249 555 316 613 371 650 313 733 251 735 253 736 334 815 254 893 333 943 255 965 227 1022 284 1116 205 1174 320 1230 376 1318 378 1336 288 1430 212 1494 276 1562 344 1597 309 1638 350 1716 272 1793 349 1809 365 1908 306 1951 464 2037 42...
output:
NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #5:
score: 0
Skipped
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #4:
0%
Subtask #8:
score: 0
Skipped
Dependency #7:
0%