제출 #931449

#제출 시각아이디문제언어결과실행 시간메모리
931449vjudge1Gym Badges (NOI22_gymbadges)C++17
51 / 100
360 ms438972 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 5e5+5, M = 5e3+3, inf = LLONG_MAX;

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

void init() {
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      dp[i][j] = inf;
    }
  }
}

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 {
    init();
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= i; j++) {
        if (dp[i][j] == inf) continue;
        
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);

        if (l[s[i].second] >= dp[i][j]) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + x[s[i].second]);
      }
    }

    for (int i = n; i >= 0; i--) {
      if (dp[n][i] != inf) {
        cout << i << "\n";
        break;
      }
    }
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...