Submission #1185448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185448		epicci23	Gym Badges (NOI22_gymbadges)	C++20	42 / 100	618 ms	1114112 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;

void _(){
  int n;
  cin >> n;
  vector<array<int,2>> v(n);
  for(int i=0;i<n;i++) cin >> v[i][0];
  for(int i=0;i<n;i++) cin >> v[i][1];
  sort(all(v),[&](array<int,2> a,array<int,2> b){
    return a[0] + a[1] < b[0] + b[1];
  });

  vector<vector<int>> dp(n+5,vector<int>(n+5,INF));
  dp[0][0] = 0;
  for(int i=1;i<=n;i++){
    for(int j=0;j<n;j++){
      if(dp[i - 1][j] == INF) continue;
      if(dp[i-1][j] <= v[i - 1][1]){
        dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]+v[i-1][0]);
      }
      dp[i][j] = min(dp[i][j], dp[i-1][j]);
    }
  }

  for(int i=n;i>=0;i--){
    if(dp[n][i] != INF){
      cout << i << '\n';
      return;
    }
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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