제출 #827170

#제출 시각아이디문제언어결과실행 시간메모리
827170tomruk카니발 티켓 (IOI20_tickets)C++17
27 / 100
652 ms52676 KiB
#include "tickets.h" #include <bits/stdc++.h> using namespace std; long long find_maximum(int k, vector<vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> answer; for (int i = 0; i < n; i++) { vector<int> row(m); for (int j = 0; j < m; j++) { row[j] = -1; } answer.push_back(row); } long long tot = 0; for(int xx = 0;xx<k;xx++){ long long maxi = -1; int opt1 = -1,opt2 = -1; for(int i = 0;i<n;i++){ int cnt = 0; for(int c = 0;c<m && cnt < 2;c+=m-xx-1){ cnt++; vector<pair<int,int>> v; for(int j = 0;j<n;j++){ if(i == j){ if(cnt == 1){ v.push_back({-2e9,j}); } else v.push_back({2e9,j}); } else{ if(x[j][m-xx-1] < x[i][c]){ v.push_back({-2e9,j}); } else if(x[j][0] > x[i][c]){ v.push_back({2e9,j}); } else v.push_back({x[j][m-xx-1]+x[j][0],j}); } } sort(v.begin(),v.end()); long long now = 0; for(int j = 0;j<n/2;j++){ now += abs(x[v[j].second][0] - x[i][c]); if(x[v[j].second][0] > x[i][c]) now = -1e18; } for(int j = n/2;j<n;j++){ now += abs(x[v[j].second][m-xx-1] - x[i][c]); if(x[v[j].second][m-xx-1] < x[i][c]) now = -1e18; } if(now > maxi){ maxi = now; opt1 = i; opt2 = cnt; } } } assert(opt1 != -1 && opt2 != -1); vector<pair<int,int>> v; for(int j = 0;j<n;j++){ if(opt1 == j){ if(opt2 == 1){ v.push_back({-2e9,j}); } else v.push_back({2e9,j}); } else{ if(x[j][m-1] < x[opt1][(opt2-1) * (m-xx-1)]){ v.push_back({-2e9,j}); } else if(x[j][0] > x[opt1][(opt2-1) * (m-xx-1)]){ v.push_back({2e9,j}); } else v.push_back({x[j][m-1]+x[j][0],j}); } } sort(v.begin(),v.end()); for(int j = 0;j<n/2;j++){ answer[v[j].second][0] = xx; x[v[j].second].erase(x[v[j].second].begin()); } for(int j = n/2;j<n;j++){ answer[v[j].second][m-1] = xx; x[v[j].second].erase(prev(x[v[j].second].end())); } tot += maxi; } allocate_tickets(answer); return tot; }
#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...