제출 #720631

#제출 시각아이디문제언어결과실행 시간메모리
720631bin9638카니발 티켓 (IOI20_tickets)C++17
25 / 100
848 ms95212 KiB
#include <bits/stdc++.h> #ifndef SKY #include "tickets.h" #endif // SKY using namespace std; #define N 1510 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back #define iii pair<ll,ii> #define iiii pair<ii,ii> int ktr[N],times,n,m,f[N]; deque<iii>cost; vector<int>lis[N][2]; #ifdef SKY void allocate_tickets(vector<vector<int>>kq) { for(int i=0;i<n;i++) { for(int j=0;j<m;j++) cout<<kq[i][j]<<" "; cout<<endl; } } #endif // SKY ll find_maximum(int k, vector<vector<int>> xxx) { n=xxx.size(); m=xxx[0].size(); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cost.pb({xxx[i][j],{i,j}}); sort(cost.begin(),cost.end()); vector<vector<int>>kq; kq.resize(n,vector<int>(m,-1)); ll res=0; int cnt=n*k/2; while(cnt>0) { iii cc=cost.back(); cost.pop_back(); if(f[cc.sc.fs]<k) { f[cc.sc.fs]++; cnt--; lis[cc.sc.fs][1].pb(cc.sc.sc); res+=cc.fs; } } // cout<<cost.size()<<endl; //return res; cnt=n*k/2; while(cnt>0) { iii cc=cost.front(); cost.pop_front(); if(f[cc.sc.fs]<k) { f[cc.sc.fs]++; cnt--; lis[cc.sc.fs][0].pb(cc.sc.sc); res-=cc.fs; } } // return 1; for(int t=0;t<k;t++) { times++; vector<int>tmp(2,n/2); for(int i=0;i<n;i++) if(ktr[i]!=times&&lis[i][1].empty()) { ktr[i]=times; tmp[0]--; kq[i][lis[i][0].back()]=t; lis[i][0].pop_back(); } for(int i=0;i<n;i++) if(ktr[i]!=times&&lis[i][0].empty()) { ktr[i]=times; tmp[1]--; kq[i][lis[i][1].back()]=t; lis[i][1].pop_back(); } for(int i=0;i<n;i++) if(ktr[i]!=times&&tmp[0]>0&&!lis[i][0].empty()) { ktr[i]=times; tmp[0]--; kq[i][lis[i][0].back()]=t; lis[i][0].pop_back(); } for(int i=0;i<n;i++) if(ktr[i]!=times&&tmp[1]>0&&!lis[i][1].empty()) { ktr[i]=times; tmp[1]--; kq[i][lis[i][1].back()]=t; lis[i][1].pop_back(); } // cout<<t<<endl; for(int i=0;i<n;i++)cout<<lis[i][0].size()<<" "<<lis[i][1].size()<<endl; } allocate_tickets(kq); return res; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,m,k; cin>>n>>m>>k; vector<vector<int>>x; x.resize(n,vector<int>(m,0)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>x[i][j]; cout<<find_maximum(k,x); return 0; } #endif
#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...