Submission #1370486

#TimeUsernameProblemLanguageResultExecution timeMemory
1370486mannshah1211Ambulance (JOI25_ambulance)C++20
27 / 100
317 ms452 KiB
// ロンリーガールはいつまでも
// 届かない夢見て
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr); 
  int l, n, t;
  cin >> l >> n >> t;
  t /= 2;
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  bool okie = false;
  for (int i = 0; i < (1 << n); i++) {
    // the mask represented by i is assigned to (1, 1) or (L, L)
    // the mask represented by ~i is assigned to (L, 1) or (1, L)
    vector<int> main, anti;
    for (int j = 0; j < n; j++) {
      if (i & (1 << j)) {
        main.push_back(x[j] + y[j]);
      } else {
        anti.push_back(x[j] - y[j]);
      }
    }
    sort(main.begin(), main.end());
    sort(anti.begin(), anti.end());
    // x[j] - 1 + L - y[j]
    int s1 = 0, s2 = 0, idx = -1;
    bool okie1 = false, okie2 = false;
    for (int j = 0; j < main.size(); j++) {
      s1 += (main[j] - 2);
      if (s1 <= t) {
        idx = j;
      }
    }
    for (int j = idx + 1; j < main.size(); j++) {
      s2 += (l + l - main[j]);
    }
    if (s2 <= t) {
      okie1 = true;
    }
    s1 = 0, s2 = 0;
    idx = -1;
    for (int j = 0; j < anti.size(); j++) {
      s1 += (l - 1) + anti[j];
      if (s1 <= t) {
        idx = j;
      }
    }
    for (int j = idx + 1; j < anti.size(); j++) {
      s2 += (l - 1) - anti[j];
    }
    if (s2 <= t) {
      okie2 = true;
    }
    if (okie1 && okie2) {
      okie = true;
    }
  }
  cout << (okie ? "Yes" : "No") << '\n';
  return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...