제출 #1238147

#제출 시각아이디문제언어결과실행 시간메모리
1238147SalihSahinCarnival Tickets (IOI20_tickets)C++20
27 / 100
330 ms86792 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<long long, long long> > > par(n+1, vector<pair<long long, long long> >(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}; } } } vector<vector<int> > ans(n, vector<int>(m, -1)); 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]; } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...