제출 #931453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931453		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	1600 ms	49028 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e5+5, S = 50, inf = LLONG_MAX;

int n, x[N], l[N];
pair<int, int> s[N];
map<int, int> dp[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }
  bool eq = 1;
  for (int i = 0; i < n; i++) {
    cin >> l[i];
    if (l[i] != l[0]) eq = 0;
  }
  for (int i = 0; i < n; i++) {
    s[i] = make_pair(x[i]+l[i], i);
  }
  sort(s, s+n);

  if (eq) {
    int ans = 0;
    int lvl = 0;
    for (int i = 0; i < n; i++) {
      int idx = s[i].second;
      if (lvl <= l[idx]) {
        ans++;
        lvl += x[idx];
      }
    }
    cout << ans << "\n";
  } 
  else {
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
      int cnt = 0;

      auto it = dp[i].end();
      while (it != dp[i].begin()) {
        if (cnt++ > S) break;

        --it;
        int j = it->first;
        int k = it->second;

        auto it2 = dp[i+1].find(j);
        if (it2 == dp[i+1].end()) dp[i+1][j] = k;
        else it2->second = min(it2->second, k);

        if (l[s[i].second] >= k) {
          it2 = dp[i+1].find(j+1);
          if (it2 == dp[i+1].end()) dp[i+1][j+1] = k + x[s[i].second];
          else it2->second = min(it2->second, k + x[s[i].second]);
        } 
      }
      dp[i].clear();
    }

    for (int i = n; i >= 0; i--) {
      if (dp[n].find(i) != dp[n].end()) {
        cout << i << "\n";
        break;
      }
    }
  }
}

• Subtask 1: 15 / 15
• Subtask 2: 9 / 9
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49