제출 #401198

#제출 시각아이디문제언어결과실행 시간메모리
401198srvlt카니발 티켓 (IOI20_tickets)C++14
27 / 100
641 ms51520 KiB
#include "tickets.h" #include <bits/stdc++.h> #define pb push_back #define all(x) begin(x),end(x) #define SZ(x) (int)(x).size() #define mem(x,y) memset(&x,y,sizeof(x)) #define ll long long using namespace std; const int n0=1503; vector<array<int,2>> pos[n0]; int r[n0],used[n0]; ll find_maximum(int k, vector<vector<int>> x) { int n=SZ(x),m=SZ(x[0]); vector<vector<int>> answer(n,vector<int>(m,-1)); vector<array<int,3>> vec; ll s=0; for(int i=0; i<n; i++) { for(int j=0; j<k; j++) { s+=x[i][j+m-k]; vec.pb({-x[i][j]-x[i][j+m-k],-j,i}); } } sort(all(vec));reverse(all(vec)); set<array<int,2>> rows; for(int i=0; i<k*n/2; i++) { s+=vec[i][0]; int x=vec[i][2],y=-vec[i][1]; rows.insert({y,x}); } for(int i=k-1; i>=0; i--) { assert(SZ(rows)>=n/2); auto it=prev(end(rows)); vector<array<int,2>> todel; for(int j=0; j<n/2; j++) { int x=(*it)[1],y=(*it)[0]; answer[x][y]=i; pos[i].pb({x,y}); todel.pb(*it); it--; } for(auto &j:todel) rows.erase(j); } for(int i=0; i<n; i++) r[i]=m-1; for(int i=0; i<k; i++) { mem(used,0); for(auto &j:pos[i]) { used[j[0]]=1; } for(int j=0; j<n; j++) { if(!used[j]) { answer[j][r[j]]=i; r[j]--; } } } allocate_tickets(answer); return s; }
#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...