제출 #428923

#제출 시각아이디문제언어결과실행 시간메모리
428923lakshith_카니발 티켓 (IOI20_tickets)C++14
0 / 100
1 ms260 KiB
#include "tickets.h" #include <bits/stdc++.h> #define ll long long #define int long long #define what_is(a) cout << #a << " is " << a << "\n" using namespace std; struct node{ int n; int MIN; int MAX; int minI; int maxI; bool what; }; bool compare(node a,node b){ return a.MIN+a.MAX < b.MIN+b.MAX; } /* long long find_maximum(signed k, std::vector<std::vector<signed>> x) { int n = x.size(); int m = x[0].size(); assert(k==1); int r = 0; vector<node> vec; for(int i=0;i<n;i++){ int MAX = -1,maxI=0; for(int j=0;j<m;j++) if(MAX<x[i][j])MAX=x[i][j],maxI=j; int MIN = INT_MAX,minI=0; for(int j=0;j<m;j++) if(MIN>x[i][j])MIN=x[i][j],minI=j; vec.push_back((node){i,MIN,MAX,minI,maxI,true}); r+=MAX; } sort(vec.begin(),vec.end(),compare); for(int i=0;i<n/2;i++){ r-=vec[i].MIN+vec[i].MAX; vec[i].what=false; } vector<vector<signed>> ans; for(int i=0;i<n;i++) ans.push_back(vector<signed>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j] = -1; for(int i=0;i<n;i++) if(vec[i].what)ans[vec[i].n][vec[i].maxI]=0; else ans[vec[i].n][vec[i].minI]=0; allocate_tickets(ans); return r; }*/ long long find_maximum(signed K, std::vector<std::vector<signed>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> ones,zeros; for(int i=0;i<n;i++){ vector<int> one,zero; for(int j=0;j<m;j++) if(x[i][j]==0)zero.push_back(j); else one.push_back(i); ones.push_back(one); zeros.push_back(zero); } vector<vector<signed>> ans; for(int i=0;i<n;i++) ans.push_back(vector<signed>(m)); for(int i=0;i<n;i++) for(int j=0;j<m;j++) ans[i][j] = -1; int r = 0; for(int k=0;k<K;k++){ int o=0,z=0; for(int i=0;i<n;i++){ if(o<n/2 && ones[i].size()>=zeros[i].size()){ if(ones[i].size()!=0){ o++; ans[i][ones[i][ones[i].size()-1]]=k; ones[i].pop_back(); r++; }else{ o++; ans[i][zeros[i][zeros[i].size()-1]]=k; zeros[i].pop_back(); } }else if(z<n/2 && zeros[i].size()>=ones[i].size()){ if(zeros[i].size()!=0){ z++; ans[i][zeros[i][zeros[i].size()-1]]=k; zeros[i].pop_back(); }else{ z++; ans[i][ones[i][ones[i].size()-1]]=k; ones[i].pop_back(); r--; } }else if(o<n/2){ if(ones[i].size()!=0){ o++; ans[i][ones[i][ones[i].size()-1]]=k; ones[i].pop_back(); r++; }else{ o++; ans[i][zeros[i][zeros[i].size()-1]]=k; zeros[i].pop_back(); } }else if(z<n/2){ if(zeros[i].size()!=0){ z++; ans[i][zeros[i][zeros[i].size()-1]]=k; zeros[i].pop_back(); }else{ z++; ans[i][ones[i][ones[i].size()-1]]=k; ones[i].pop_back(); r--; } } } } allocate_tickets(ans); return r; }
#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...