제출 #992217

#제출 시각아이디문제언어결과실행 시간메모리
992217inventiontimeGym Badges (NOI22_gymbadges)C++17
15 / 100
512 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; #define int ll #define endl '\n' //comment for interactive #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pb push_back #define re resize #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define all1(x) (x).begin()+1, (x).end() #define loop(i, n) for(int i = 0; i < n; i++) #define loop1(i, n) for(int i = 1; i <= n; i++) #define print(x) cout << #x << ": " << x << endl << flush typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; typedef array<int, 3> ti; typedef vector<ii> vii; typedef vector<ti> vti; typedef vector<vi> vvi; typedef priority_queue<int> pq; template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; } template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; } const int inf = 1e17; const int maxn = 5005; void solve() { int n; cin >> n; vti g(n+1); loop1(i, n) cin >> g[i][1]; // x loop1(i, n) cin >> g[i][2]; // l loop1(i, n) g[i][0] = g[i][1] + g[i][2]; sort(all1(g)); vvi dp(n+1, vi(n+1, inf)); loop(i, n+1) loop(j, n+1) dp[i][j] = inf; loop(i, n+1) dp[0][0] = 0; loop1(i, n) { loop1(j, n) { if(dp[i-1][j-1] <= g[i][2]) ckmin(dp[i][j], dp[i-1][j-1] + g[i][1]); ckmin(dp[i][j], dp[i-1][j]); } } int res = 0; loop1(i, n) if(dp[n][i] < inf) res = i; cout << res << endl; } signed main() { fast_io; int t = 1; //cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...