Submission #1315046

#TimeUsernameProblemLanguageResultExecution timeMemory
1315046samarthkulkarniGym Badges (NOI22_gymbadges)C++20
42 / 100
94 ms196988 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define vi vector<long long> #define all(x) x.begin(), x.end() #define endl "\n" #define pr pair<ll, ll> #define ff first #define ss second void solution(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); solution(); return 0; } const int N = 5e3+10; pr a[N]; ll dp[N][N]; void solution() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) dp[i][j] = 1e18; } ll n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].ss; for (int i = 1; i <= n; i++) cin >> a[i].ff; sort(a+1, a+n+1, [&](pr p1, pr p2) { return (p1.ff + p1.ss) < (p2.ff + p2.ss); }); dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= i; j++) { dp[i][j] = dp[i-1][j]; if (a[i].ff >= dp[i-1][j-1]) { dp[i][j] = min(dp[i][j], dp[i-1][j-1] + a[i].ss); } } } for (int i = n; i >= 0; i--) { if (dp[n][i] != 1e18) { cout << i << endl; return; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...