QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185022 | #4906. 球球 | hos_lyric# | 0 | 2ms | 6796kb | C++14 | 2.5kb | 2023-09-21 15:59:39 | 2024-07-04 02:06:15 |
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
int N;
vector<Int> T, X;
Int dist(int i, int j) {
return abs(X[i] - X[j]);
}
namespace brute {
bitset<5010> dp[5010];
bool run() {
for (int i = 0; i <= N; ++i) {
dp[i].reset();
}
dp[0][0] = true;
for (int i = 0; i < N; ++i) if (dp[i][i]) {
// cerr<<i<<": ";for(int j=0;j<=N;++j)cerr<<dp[i][j];cerr<<endl;
// go
if (dist(i, i + 1) <= T[i + 1] - T[i]) {
dp[i + 1] |= dp[i];
for (int j = i + 1; j <= N; ++j) {
if (dist(i, j) + dist(j, i + 1) <= T[i + 1] - T[i]) {
dp[i + 1][j] = true;
}
}
}
// clone
if (dp[i][i + 1]) {
if (X[i + 1] == X[N]) {
return true;
}
for (int ii = i + 1; X[i + 1] == X[ii]; ++ii) {
for (int j = ii + 1; j <= N; ++j) {
if (max(dist(i, j), T[ii] - T[i]) + dist(j, ii + 1) <= T[ii + 1] - T[i]) {
dp[ii + 1][j] = true;
}
}
}
}
}
return dp[N][N];
}
} // brute
int main() {
for (; ~scanf("%d", &N); ) {
T.resize(N + 1);
X.resize(N + 1);
for (int i = 1; i <= N; ++i) {
scanf("%lld%lld", &T[i], &X[i]);
}
T[0] = 0;
X[0] = 0;
const bool ans = brute::run();
puts(ans ? "YES" : "NO");
}
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: 0ms
memory: 3768kb
input:
5 2 1 3 2 9 6 10 5 13 -1
output:
NO
result:
ok single line: 'NO'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
5 1 1 3 2 4 -1 6 4 10 -1
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
4 16 13 18 4 20 3 21 5
output:
NO
result:
ok single line: 'NO'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
5 2 1 3 2 8 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 2 1 3 2 9 6 10 5 13 0
output:
YES
result:
ok single line: 'YES'
Test #6:
score: -5
Wrong Answer
time: 0ms
memory: 3772kb
input:
5 1 1 3 2 4 0 6 4 10 -1
output:
NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #91:
score: 0
Wrong Answer
time: 2ms
memory: 6796kb
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%