제출 #779385

#제출 시각아이디문제언어결과실행 시간메모리
779385jasmin카니발 티켓 (IOI20_tickets)C++17
27 / 100
426 ms51444 KiB
#include "tickets.h" #include<bits/stdc++.h> using namespace std; long long solvem1(int n, int k, vector<vector<int> >& x){ vector<int> s(n); for(int i=0; i<n; i++){ s[i]=x[i][0]; } sort(s.begin(), s.end()); int mi=s[n/2]; long long ans=0; for(int i=0; i<n; i++){ if(s[i]<mi){ ans += mi-s[i]; } else{ ans += s[i]-mi; } } return ans; } long long solvek1(int n, int m, int k, vector<vector<int> >& x, vector<vector<int> >& answer){ vector<int> minind(n, 0); vector<int> maxind(n, 0); for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ if(x[i][j] < x[i][minind[i]]){ minind[i]=j; } if(x[i][j] > x[i][maxind[i]]){ maxind[i]=j; } } } vector<int> nums; for(int i=0; i<n; i++){ nums.push_back(x[i][maxind[i]]); nums.push_back(x[i][minind[i]]); } sort(nums.begin(), nums.end()); int mi=nums[n-1]; for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ answer[i][j] = -1; } answer[i][maxind[i]]=0; } vector<pair<long long,int> > sorted; long long ans=0; int cntsmall=0; for(int i=0; i<n; i++){ if(x[i][maxind[i]]<mi){ answer[i][maxind[i]]=-1; answer[i][minind[i]]=0; ans += mi - x[i][minind[i]]; cntsmall++; continue; } if(x[i][minind[i]]>mi){ ans += x[i][maxind[i]]-mi; continue; } assert(x[i][minind[i]]<=mi && mi<=x[i][maxind[i]]); int vsmall = mi - x[i][minind[i]]; int vbig = x[i][maxind[i]] - mi; ans += vbig; long long gain = vsmall - vbig; sorted.push_back({gain, i}); } sort(sorted.begin(), sorted.end()); reverse(sorted.begin(), sorted.end()); for(int i=0; cntsmall<n/2; i++, cntsmall++){ long long gain=sorted[i].first; int ind=sorted[i].second; ans += gain; answer[ind][maxind[ind]]=-1; answer[ind][minind[ind]]=0; } return ans; } long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int> > answer(n, vector<int> (m, -1)); long long ans=0; if(m==1){ for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ answer[i][j]=0; } } ans=solvem1(n, k, x); } else if(k==1){ ans=solvek1(n, m, k, x, answer); } allocate_tickets(answer); 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...