Submission #1127808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127808		JelalTkm	Tug of War (BOI15_tug)	C++20	41 / 100	216 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(2 * n + 1);
    vector<int> cnt_l(n + 1), cnt_r(n + 1), cnt(n + 1);
    int sm = 0;
    for (int i = 1; i <= 2 * n; 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 == 2 * n) {
      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<vector<pair<int, int>>>> dp(n + 1, vector<vector<pair<int, int>>> (((sm + 3) >> 1), vector<pair<int, int>> (n + 1)));
    for (int i = 1; i <= n; i++) {
      dp[0][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 <= 2 * n; i++) {
      int in = a[i].first;
      for (int j = a[i].second.second; j <= ((sm + 1) >> 1); j++) {
        if (dp[in - 1][j - a[i].second.second][a[i].second.first].first && (cnt_r[a[i].second.first] + cnt[a[i].second.first]) - (dp[in - 1][j - a[i].second.second][a[i].second.first].second + 1) > 0) {
          dp[in][j] = dp[in - 1][j - a[i].second.second];
          dp[in][j][a[i].second.first].second += 1;
          if (in == n && abs((sm - j) - j) <= ko)
            ans = "YES";
        }
      }
    }

    cout << ans << '\n';
  }
 
  return 0;
}

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