Submission #817806

#TimeUsernameProblemLanguageResultExecution timeMemory
817806cig32Akcija (COCI21_akcija)C++17
10 / 110
3 ms1624 KiB
#include "bits/stdc++.h" using namespace std; #define int long long #define double long double const int MAXN = 1e5 + 10; const int MOD = 1e9 + 7; mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } int bm(int b, int p) { if(p==0) return 1 % MOD; int r = bm(b, p >> 1); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } int inv(int b) { return bm(b, MOD-2); } int fastlog(int x) { return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1); } void printcase(int i) { cout << "Case #" << i << ": "; } bool cmp(pair<int, int> x, pair<int, int> y) { return x.second < y.second; } bool cmp2(pair<int, int> x, pair<int, int> y) { if(x.first == y.first) return x.second < y.second; return x.first > y.first; } void solve(int tc) { int n, k; cin >> n >> k; pair<int, int> p[n+1]; for(int i=1; i<=n; i++) cin >> p[i].first >> p[i].second; sort(p+1, p+1+n, cmp); pair<int, int> dp[n+1][k+1]; for(int i=1; i<=n; i++) { for(int j=1; j<=k; j++) { dp[i][j] = {-1e18, 1e18}; } } for(int i=2; i<=k; i++) dp[0][i] = {-1e18, 1e18}; dp[0][1] = {0, 0}; pair<int, int> pre[k+1]; for(int i=1; i<=k; i++) pre[i] = {-1e18, 1e18}; pre[1] = {0, 0}; for(int i=1; i<=n; i++) { pair<int, int> res[k+1]; vector<pair<int, int> >nw; for(int j=1; j<=k; j++) { if(p[i].second >= pre[j].first + 1) { nw.push_back({pre[j].first + 1, pre[j].second + p[i].first}); } } for(int j=0; j<min(k, (int) nw.size()); j++) { dp[i][j+1] = nw[j]; } int p1=1, p2=1; for(int j=1; j<=k; j++) { if(pre[p1].first > dp[i][p2].first) { res[j] = pre[p1++]; } else if(pre[p1].first < dp[i][p2].first) { res[j] = dp[i][p2++]; } else if(pre[p1].second < dp[i][p2].second) { res[j] = pre[p1++]; } else { res[j] = dp[i][p2++]; } } for(int j=1; j<=k; j++) pre[j] = res[j]; } vector<pair<int, int> > sol; for(int i=0; i<=n; i++) { for(int j=1; j<=k; j++) { if(dp[i][j].second <= 1e13) sol.push_back(dp[i][j]); } } sort(sol.begin(), sol.end(), cmp2); for(int i=0; i<k; i++) cout << sol[i].first << ' ' << sol[i].second << "\n"; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); } // 勿忘初衷
#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...