제출 #337457

#제출 시각아이디문제언어결과실행 시간메모리
337457MvC카니발 티켓 (IOI20_tickets)C++14
11 / 100
2 ms836 KiB
#include "tickets.h" #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second #define all(x) x.begin(),x.end() #define lun(x) (int)x.size() typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<60); const int inf=(1<<30); const int nmax=2e3+50; const ll mod=1e9+7; using namespace std; int n,m,i,j,nr,vz[nmax],t,l[nmax],f[nmax]; vector<vector<int> >rs; vector<pair<int,pair<int,int> > >vc; vector<int>v[2][nmax]; vector<pair<int,int> >ea,eb,fft; set<pair<int,int> >s,b; set<pair<int,int> >::iterator it; ll sm; ll find_maximum(int k,vector<vector<int> > a) { n=lun(a),m=lun(a[0]); /*for(i=0;i<n;i++)for(j=0;j<m;j++)vc.pb(mkp(a[i][j],mkp(i,j))); sort(all(vc)); for(i=0;i<n*m;i++) { v[i<n*m/2][vc[i].sc.fr].pb(vc[i].sc.sc); if(i<n*m/2)sm-=1LL*vc[i].fr; else sm+=1LL*vc[i].fr; } for(i=0;i<n;i++) { if(!v[0][i].empty())b.in(mkp(lun(v[0][i]),i)); if(!v[1][i].empty())s.in(mkp(lun(v[1][i]),i)); }*/ rs.resize(n); for(i=0;i<n;i++)for(j=0;j<m;j++)rs[i].pb(-1); for(i=0;i<n;i++)l[j]=m-1; for(i=0;i<k;i++) { fft.clear(); for(j=0;j<n;j++) { fft.pb(mkp(a[j][l[j]],j)); } sort(all(fft)); for(j=0;j<n/2;j++) { t=fft[j].sc; rs[t][f[t]]=i; sm-=1LL*a[t][f[t]++]; } for(;j<n;j++) { t=fft[j].sc; rs[t][l[t]]=i; sm+=1LL*a[t][l[t]--]; } /*for(j=0;j<n;j++)vz[j]=0; nr=0; ea.clear(),eb.clear(); it=--s.end(); for(j=0;j<n/2;j++) { t=it->sc; rs[t][v[1][t].back()]=i; v[1][t].pop_back(); vz[t]=1; ea.pb(*it); it--; } it=--b.end(); for(j=0;j<n/2;j++) { while(vz[it->sc])it--; t=it->sc; rs[t][v[0][t].back()]=i; v[0][t].pop_back(); vz[t]=1; eb.pb(*it); it--; } for(j=0;j<lun(ea);j++) { s.er(s.fd(ea[j])); if(ea[j].fr>1)s.in(mkp(ea[j].fr-1,ea[j].sc)); } for(j=0;j<lun(eb);j++) { b.er(b.fd(eb[j])); if(eb[j].fr>1)b.in(mkp(eb[j].fr-1,eb[j].sc)); }*/ } allocate_tickets(rs); return sm; } /*int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); 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...