Submission #1225458

#TimeUsernameProblemLanguageResultExecution timeMemory
1225458PVM_pvmCarnival Tickets (IOI20_tickets)C++20
100 / 100
466 ms63248 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define MAXN 1502 int N,M; int alc[MAXN][MAXN]; ///0 e nishto, 1 e minus, 2 e plus int brm[MAXN]; int brp[MAXN]; struct state { long long vl; int ind; }; bool operator>(state a, state b) { return a.vl>b.vl; } bool operator<(state a, state b) { return a.vl<b.vl; } bool cmp(int a, int b) { return brp[a]>brp[b]; } int lst[MAXN]; int fr[MAXN]; long long find_maximum(int k, vector<vector<int>> x) { int n = x.size(); N=n; int m = x[0].size(); M=m; vector<vector<int>> ans; for (int q=0;q<n;q++) { vector<int> ans2; ans2.resize(m); for (int w=0;w<m;w++) ans2[w]=-1; ans.push_back(ans2); } long long otg=0; for (int q=0;q<n;q++) { brm[q]=k; brp[q]=0; lst[q]=m-1; fr[q]=0; for (int w=0;w<k;w++) { alc[q][w]=1; otg-=x[q][w]; } } //cout<<otg<<"\n"; priority_queue<state> qu; for (int q=0;q<n;q++) { state cur={x[q][m-1]+x[q][k-1],q}; qu.push(cur); } for (int klk=0;klk<(n*k/2);klk++) { state tp=qu.top(); qu.pop(); //cout<<tp.vl<<" "<<tp.ind<<"\n"; otg+=tp.vl; alc[tp.ind][ brm[ tp.ind ] ]=0; brm[ tp.ind ]--; alc[ tp.ind ][ m-1-brp[tp.ind] ]=2; brp[ tp.ind ]++; //cout<<brm[tp.ind]<<" "<<brp[tp.ind]<<" sa veche\n"; if (brm[tp.ind]==0) continue; state nxt={ x[tp.ind][brm[tp.ind]-1]+x[tp.ind][ m-1-brp[tp.ind] ] ,tp.ind}; qu.push(nxt); } vector<int> zasr; for (int q=0;q<n;q++) zasr.push_back(q); for (int cur=0;cur<k;cur++) { sort(zasr.begin(),zasr.end(),cmp); for (int q=0;q<(n/2);q++) { ans[ zasr[q] ][ lst[ zasr[q] ] ]=cur; lst[ zasr[q] ]--; brp[ zasr[q] ]--; } for (int q=(n/2);q<n;q++) { ans[ zasr[q] ][ fr[ zasr[q] ] ]=cur; brm[zasr[q]]--; fr[ zasr[q] ]++; } } allocate_tickets(ans); return otg; }
#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...