Submission #1168016

#TimeUsernameProblemLanguageResultExecution timeMemory
1168016irmuunCarnival Tickets (IOI20_tickets)C++17
100 / 100
454 ms54380 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() ll find_maximum(int k,vector<vector<int>>x){ int n=x.size(),m=x[0].size(); auto s=vector(n,vector<int>(m,-1)); priority_queue<pair<int,int>>p; ll ans=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(j<k){ ans-=(ll)x[i][j]; if(j==k-1) p.push({x[i][j]+x[i][j+m-k],i}); } } } vector<int>r(n,k-1); vector<int>L(n,0),R(n,m-1); for(int c=0;c<n*k/2;c++){ auto [add,i]=p.top(); ans+=(ll)add; p.pop(); r[i]--; if(r[i]>=0) p.push({x[i][r[i]]+x[i][r[i]+m-k],i}); } vector<pair<int,int>>cnt; for(int i=0;i<n;i++){ cnt.pb({k-r[i]-1,i}); } for(int i=0;i<k;i++){ sort(rall(cnt)); for(int j=0;j<n;j++){ if(j<n/2){ s[cnt[j].ss][R[cnt[j].ss]--]=i; cnt[j].ff--; } else{ s[cnt[j].ss][L[cnt[j].ss]++]=i; } } } allocate_tickets(s); return ans; }
#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...