제출 #767755

#제출 시각아이디문제언어결과실행 시간메모리
767755drdilyorAkcija (COCI21_akcija)C++17
30 / 110
87 ms63188 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; signed main() { cin.tie(0)->sync_with_stdio(0); int n, k; cin >> n >> k; vector<pair<int,int>> arr(n); for (auto&[d, cost] : arr) cin >> cost >> d; // assert(k == 1); sort(arr.begin(), arr.end()); vector memo(n, vector(n+1, pair{-1, 0ll})); auto dp = [&](auto& dp, int i, int t)->pair<int,ll> { if (i < 0 || t <= 0) return {0, 0}; if (memo[i][t].first != -1) return memo[i][t]; auto res = dp(dp, i-1, t); if (arr[i].first >= t) { auto [cnt, cost] = dp(dp, i-1, t-1); cnt++; cost -= arr[i].second; res = max(res, {cnt, cost}); } return memo[i][t] = res; }; pair<int,ll> res = {0, 0}; for (int i = 1; i <= n; i++) { res = max(res, dp(dp, n-1, i)); } cout << res.first << ' ' << -res.second << endl; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...