QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185022#4906. 球球hos_lyric#0 2ms6796kbC++142.5kb2023-09-21 15:59:392024-07-04 02:06:15

Judging History

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

  • [2024-07-04 02:06:15]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:6796kb
  • [2023-09-21 15:59:39]
  • 提交

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%