Submission #1127817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127817		JelalTkm	Tug of War (BOI15_tug)	C++20	41 / 100	230 ms	327680 KiB

tug

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
using namespace std;
 
#define int long long int
 
const int N = 2e1 + 10;
const int md = 1e9 + 7;
const int INF = 1e9;
 
int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int T = 1;
  // cin >> T;
  while (T--) {
    int n, ko;
    cin >> n >> ko;
    vector<pair<int, pair<int, int>>> a((n << 1) + 1);
    vector<int> cnt_l(n + 1), cnt_r(n + 1), cnt(n + 1);
    int sm = 0;
    for (int i = 1; i <= (n << 1); i++) {
      cin >> a[i].first >> a[i].second.first >> a[i].second.second;
      if (a[i].first == a[i].second.first)
        cnt[a[i].first]++;
      else {
        cnt_l[a[i].first]++;
        cnt_r[a[i].second.first]++;
      }
      sm += a[i].second.second;
    }
 
    if (sm == (n << 1)) {
      for (int i = 1; i <= n; i++)
        if (cnt[i] + cnt_r[i] + cnt_l[i] <= 1 || cnt[i] + cnt_r[i] == 0 || cnt[i] + cnt_l[i] == 0) {
          cout << "NO" << '\n';
          return 0;
        }
      cout << "YES" << '\n';
      continue;
    }
 
    sort(a.begin(), a.end());
    vector<vector<pair<int, int>>> dp(((sm + 3) >> 1), vector<pair<int, int>> (n + 1)), dp1(((sm + 3) >> 1), vector<pair<int, int>> (n + 1));
    for (int i = 1; i <= n; i++) {
      dp1[0][i] = make_pair(1, 0);
      if (cnt[i] + cnt_r[i] + cnt_l[i] <= 1 || cnt[i] + cnt_r[i] == 0 || cnt[i] + cnt_l[i] == 0) {
        cout << "NO" << '\n';
        return 0;
      }
    }
 
    string ans = "NO";
    for (int i = 1; i <= (n << 1); i++) {
      int in = a[i].first;
      for (int j = a[i].second.second; j <= ((sm + 1) >> 1); j++) {
        if (dp1[j - a[i].second.second][a[i].second.first].first && (cnt_r[a[i].second.first] + cnt[a[i].second.first]) - (dp1[j - a[i].second.second][a[i].second.first].second + 1) > 0) {
          for (int k = 1; k <= n; k++) {
            dp[j][k] = dp1[j - a[i].second.second][k];
            dp[j][k].second += (k == a[i].second.first);
            if (in == n && abs((sm - j) - j) <= ko)
              ans = "YES";
          }
        }
      }
      if (i + 1 <= ((n << 1)) && a[i].first != a[i + 1].first)
        swap(dp, dp1);
    }
 
    cout << ans << '\n';
  }
 
  return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29