Submission #1238202

#TimeUsernameProblemLanguageResultExecution timeMemory
1238202SalihSahinCarnival Tickets (IOI20_tickets)C++20
27 / 100
321 ms69236 KiB
#include "bits/stdc++.h" #include "tickets.h" #define pb push_back using namespace std; const long long inf = 1e15; long long find_maximum(int k, vector<vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> ans(n, vector<int>(m, -1)); if(m == 1){ long long val = 0; vector<int> arr; for(int i = 0; i < n; i++){ arr.pb(x[i][0]); val += x[i][0]; ans[i][0] = 0; } sort(arr.begin(), arr.end()); for(int i = 0; i < n/2; i++){ val -= arr[i] * 2; } allocate_tickets(ans); return val; } else if(k == 1){ vector<int> mini(n), maxi(n); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(x[i][j] > x[i][maxi[i]]){ maxi[i] = j; } if(x[i][j] < x[i][mini[i]]){ mini[i] = j; } } } vector<vector<long long> > dp(n+1, vector<long long>(n/2+2, -inf)); vector<vector<pair<int, int> > > par(n+1, vector<pair<int, int> >(n/2+2)); dp[0][0] = 0; for(int i = 0; i < n; i++){ for(int j = 0; j <= min(i, n/2); j++){ if(dp[i][j] + x[i][maxi[i]] > dp[i+1][j+1]){ dp[i+1][j+1] = dp[i][j] + x[i][maxi[i]]; par[i+1][j+1] = {i, j}; } if(dp[i][j] - x[i][mini[i]] > dp[i+1][j]){ dp[i+1][j] = dp[i][j] - x[i][mini[i]]; par[i+1][j] = {i, j}; } } } pair<int, int> now = {n, n/2}; while(now != make_pair(0, 0)){ pair<int, int> nxt = par[now.first][now.second]; if(now.second == nxt.second){ ans[nxt.first][mini[nxt.first]] = 0; } else{ ans[nxt.first][maxi[nxt.first]] = 0; } now = nxt; } allocate_tickets(ans); return dp[n][n/2]; } vector<vector<long long> > dp(n+1, vector<long long>(n*k/2 + 2, -inf)); vector<vector<pair<int, int> > > par(n+1, vector<pair<int, int> >(n*k/2+2)); dp[0][0] = 0; for(int i = 0; i < n; i++){ vector<pair<int, int> > arr; for(int j = 0; j < m; j++){ arr.pb({x[i][j], j}); } sort(arr.begin(), arr.end()); vector<long long> add(k+1); long long now = 0; for(int j = 0; j <= k; j++){ now -= arr[j].first; } add[0] = now; for(int j = 0; j < k; j++){ now += arr[(k - j)].first; now += arr[m - j - 1].first; add[j+1] = now; } for(int take = 0; take <= k; take++){ for(int j = 0; j + take <= n*k/2; j++){ if(dp[i+1][j + take] < dp[i][j] + add[take]){ dp[i+1][j + take] = dp[i][j] + add[take]; par[i+1][j + take] = {i, j}; } } } } int lstsm = 0, lstbg = k-1; pair<int, int> now = {n, n*k/2}; while(now != make_pair(0, 0)){ pair<int, int> nxt = par[now.first][now.second]; int big = now.second - nxt.second; int small = k - big; vector<pair<int, int> > arr; for(int j = 0; j < m; j++){ arr.pb({x[nxt.first][j], j}); } sort(arr.begin(), arr.end()); for(int i = 0; i < small; i++){ ans[nxt.first][arr[i].second] = lstsm++; if(lstsm == k) lstsm -= k; } for(int i = m-1; i >= m-big; i--){ ans[nxt.first][arr[i].second] = lstbg--; if(lstbg == -1) lstbg += k; } now = nxt; } allocate_tickets(ans); return dp[n][n*k/2]; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...