제출 #409460

#제출 시각아이디문제언어결과실행 시간메모리
409460achibasadzishvili카니발 티켓 (IOI20_tickets)C++17
27 / 100
639 ms52484 KiB
#include "tickets.h" #include <vector> #include<bits/stdc++.h> #define ll long long #define f first #define s second #define pb push_back using namespace std; ll l[50005],r[50005],t[50005],ind[50005]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = (int)x.size() , m = (int)x[0].size(); vector<vector<int> >ans; vector<int>g; ll pas = 0; for(int i=0; i<m; i++) g.pb(-1); for(int i=0; i<n; i++)ans.pb(g); for(int i=0; i<k; i++){ t[i] = m - 1 - (k - i - 1); } set<pair<ll,ll> >st; for(int i=0; i<n; i++){ sort(x[i].begin() , x[i].end()); for(int j=0; j<k; j++){ pas -= x[i][j]; } ind[i] = k - 1; st.insert({x[i][ind[i]] + x[i][t[ind[i]]] , i}); } ll raod = n * k / 2; while(raod--){ pair<ll,ll>p = *(--st.end()); pas += p.f; st.erase(st.find(p)); ll a = p.s; ind[a]--; if(ind[a] >= 0){ st.insert({x[a][ind[a]] + x[a][t[ind[a]]] , a}); } } for(int i=0; i<n; i++){ l[i] = 0; r[i] = m - 1; } for(int val=0; val<k; val++){ vector<pair<int,int> >v; for(int i=0; i<n; i++){ v.pb({ind[i] , i}); } sort(v.begin() , v.end()); int P = 0; for(auto to : v){ P++; int i = to.s; if(P > n / 2){ ans[i][l[i]] = val; l[i]++; } else{ ans[i][r[i]] = val; r[i]--; } } } allocate_tickets(ans); return pas; }
#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...