Submission #1218343

#TimeUsernameProblemLanguageResultExecution timeMemory
1218343brintonCarnival Tickets (IOI20_tickets)C++20
62 / 100
2779 ms2162688 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; long long m_allocate_tickets(vector<vector<int>> answer,vector<vector<int>> x){ allocate_tickets(answer); // find k; int N = answer.size(); int k = 0; for(auto &i:answer[0]) k = max(i+1,k); vector<vector<int>> cards(k); for(int i = 0;i < N;i++){ for(int j = 0;j < answer[0].size();j++){ if(answer[i][j] != -1) cards[answer[i][j]].push_back(x[i][j]); } } long long ans = 0; for(auto v:cards) { sort(v.begin(),v.end()); for(int i = 0;i < N;i++){ if(i < N/2){ ans -= v[i]; }else{ ans += v[i]; } } } return ans; } #define inf (long long)(1e15) long long find_maximum(int k, vector<vector<int>> x) { vector<vector<int>> cx = x; int N = x.size(); int M = x[0].size(); vector<vector<int>> backtrack(N,vector<int>(N*k/2+1));// dp[round][take+]; vector<long long> dp(N*k/2+1,-inf); dp[0] = 0; for(int i = 0;i < N;i++){ vector<long long> take(k+1); for(int j = 0;j < k;j++){ take[0] -= x[i][j]; } for(int j = 1;j <= k;j++){ take[j] = take[j-1]+x[i][M-j]+x[i][k-j]; } vector<long long> ndp(N*k/2+1); for(int j = 0;j <= N*k/2;j++){ backtrack[i][j] = 0; ndp[j] = dp[j]+take[0]; for(int tk = 1;tk <= k;tk++){ if(j-tk < 0) break; if(dp[j-tk]+take[tk] > ndp[j]){ ndp[j] = dp[j-tk]+take[tk]; backtrack[i][j] = tk; } } } swap(dp,ndp); } vector<int> ones(N,0); x = vector<vector<int>>(N,vector<int>(M,0)); { int cur = N*k/2; for(int i = N-1;i >= 0;i--){ ones[i] = backtrack[i][cur]; for(int d = 0;d < ones[i];d++){ x[i][M-d-1] = 1; } cur -= backtrack[i][cur]; } } // for(auto &i:ones) cout << i << " "; vector<vector<int>> answer(N,vector<int>(M,-1)); vector<int> fpt(N,0); vector<int> bpt(N,M-1); for(int ck = 0;ck < k;ck++){ // for(auto &i:ones) cout << i << " ";cout << endl; vector<pair<int,int>> colors;// cone,idx; for(int i = 0;i < N;i++){ colors.push_back({ones[i],i}); } sort(colors.begin(),colors.end()); for(int i = 0;i < N;i++){ // cout << type[i]; auto [cone,cidx] = colors[i]; if(i < N/2){// take zero answer[cidx][fpt[cidx]] = ck; ones[cidx] -= x[cidx][fpt[cidx]]; fpt[cidx]++; }else{// take one answer[cidx][bpt[cidx]] = ck; ones[cidx] -= x[cidx][bpt[cidx]]; bpt[cidx]--; } } } return m_allocate_tickets(answer,cx); }
#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...