제출 #1205419

#제출 시각아이디문제언어결과실행 시간메모리
1205419ansori카니발 티켓 (IOI20_tickets)C++20
100 / 100
914 ms174704 KiB
#include "tickets.h" #include <bits/stdc++.h> #define fi first #define se second using namespace std; void allocate_tickets(vector<vector<int>> _d) ; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<std::vector<int>> answ(n , vector<int> (m , -1)); vector<pair<int , pair<int , int>>> vc; set<int> st[n]; for(int i = 0;i < n; ++ i){ for(int j = m - 1;j >= m - k; -- j){ st[i].insert(m - 1 - j); vc.push_back({x[i][j] + x[i][j - m + k] , {i , j}}); } //cout << '\n'; } // авававааавава sort(vc.rbegin() , vc.rend()); long long ans = 0; vector<int> ps(n , m) , f(k + 1 , 0) , d(n , 0); vector<int> pq; for(int i = 0;i < (n / 2) * k; ++ i){ ans += x[vc[i].se.fi][vc[i].se.se]; //cout << vc[i].se.fi << ' ' << vc[i].se.se << '\n'; pq.push_back(vc[i].se.fi); } sort(pq.begin() , pq.end()); int kol = 0; for(auto i : pq){ ps[i] --; int p = ps[i]; int day = kol % k; kol ++; answ[i][p] = day; st[i].erase(day); } reverse(vc.begin() , vc.end()); vector<int> pos(n , 0); for(int i = 0;i < (n / 2) * k; ++ i){ int p = pos[vc[i].se.fi]; pos[vc[i].se.fi] ++; ans -= x[vc[i].se.fi][p]; // cout << vc[i].se.fi << ' ' << p << '\n'; answ[vc[i].se.fi][p] = *(st[vc[i].se.fi].begin()); st[vc[i].se.fi].erase(st[vc[i].se.fi].begin()); } allocate_tickets(answ); 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...