Submission #1370513

#TimeUsernameProblemLanguageResultExecution timeMemory
1370513mannshah1211Ambulance (JOI25_ambulance)C++20
0 / 100
9 ms436 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];
  }
  sort(x.begin(), x.end());
  bool okie = false;
  for (int i = 0; i <= n; i++) {
    vector<bool> dp_pref(t + 1);
    dp_pref[0] = true;
    for (int j = 0; j < i; j++) {
      for (int k = t; k >= x[i] + y[i] - 2; k--) {
        if (dp_pref[k - (x[i] + y[i] - 2)]) {
          dp_pref[k] = true;
        }
      }
    }
    vector<bool> dp_suff(t + 1);
    dp_suff[0] = true;
    for (int j = n - 1; j >= i; j--) {
      for (int k = t; k >= 2 * l - (x[i] + y[i]); k--) {
        if (dp_suff[k - (2 * l - (x[i] + y[i]))]) {
          dp_suff[k] = true;
        }
      }
    }
    int sum_pref = 0, sum_suff = 0;
    for (int j = 0; j < n; j++) {
      sum_pref += (x[i] + y[i] - 2), sum_suff += (2 * l) - (x[i] + y[i]);
    }
    bool okie1 = false, okie2 = false;
    for (int k = 0; k <= t; k++) {
      if (sum_pref - k >= 0 && sum_pref - k <= t && dp_pref[sum_pref - k]) {
        okie1 = true;
      }
    }
    for (int k = 0; k <= t; k++) {
      if (sum_suff - k >= 0 && sum_suff - k <= t && dp_suff[sum_suff - k]) {
        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...