Submission #1078918

#TimeUsernameProblemLanguageResultExecution timeMemory
1078918UmairAhmadMirzaCarnival Tickets (IOI20_tickets)C++17
27 / 100
398 ms73216 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int const N=1505; bool od[N]; bool temp[N]; void allocate_tickets(vector<vector<int>> _x); ll fun(ll val,vector<pair<int,int>> &pr){ int n=pr.size(); int lw=n/2,hg=n/2; ll ans=0; vector<pair<ll,int>> diff; for(int i=0;i<n;i++){ auto [mn,mx]=pr[i]; if(mx<=val){ lw--; ans+=val-mn; } else if(mn>val){ hg--; ans+=mx-val; temp[i]=1; } else{ ans+=min(mx-val,val-mn); diff.push_back({((mx-val)-(val-mn)),i}); } } if(hg<0 || lw<0 || hg+lw!=diff.size()) return -1; // cout<<ans<<endl; // cout<<lw<<' '<<hg<<endl; sort(diff.begin(),diff.end()); // for(int i=0;i<diff.size();i++){ // cout<<diff[i].first<<' '<<diff[i].second<<endl; // } for(int i=0;i<lw;i++) ans+=max(0LL,-diff[i].first); reverse(diff.begin(),diff.end()); for(int i=0;i<hg;i++){ ans+=max(0LL,diff[i].first); temp[diff[i].second]=1; } return ans; } ll yep_round(vector<pair<int,int>> &pr){ int n=pr.size(); for (int i = 0; i < n; ++i){ od[i]=0; temp[i]=0; } ll cur=0; vector<int> all; for(auto [x,y]:pr){ all.push_back(x); // all.push_back(y-1); } for(int i:all){ for(int j=0;j<n;j++) temp[j]=0; ll c=fun(i,pr); // cout<<endl; // cout<<i<<' '<<c<<endl; // for(int j=0;j<n;j++) // cout<<temp[j]<<' '; // cout<<endl; if(c>=cur){ cur=c; for(int j=0;j<n;j++) od[j]=temp[j]; } } vector<int> v; cur=0; for(int i=0;i<n;i++){ if(od[i]) v.push_back(pr[i].second); else v.push_back(pr[i].first); } sort(v.begin(),v.end()); for(int i=0;i<n;i++) cur+=abs(v[n/2]-v[i]); // cout<<cur<<endl; return cur; } long long find_maximum(int k, vector<vector<int>> d){ vector<int> all; int n=d.size(); int m=d[0].size(); vector<vector<int>> x=d; for(int i=0;i<n;i++) for(int j=0;j<m;j++) x[i][j]=-1; ll ans=0; int p1[n],p2[n]; for(int i=0;i<n;i++){ p1[i]=0; p2[i]=m-1; } for(int r=0;r<k;r++){ vector<pair<int,int>> pr; for(int i=0;i<n;i++) pr.push_back({d[i][p1[i]],d[i][p2[i]]}); ans+=yep_round(pr); for(int i=0;i<n;i++){ if(od[i]){ x[i][p2[i]]=r; p2[i]--; } else{ x[i][p1[i]]=r; p1[i]++; } } } allocate_tickets(x); return ans; }

Compilation message (stderr)

tickets.cpp: In function 'long long int fun(long long int, std::vector<std::pair<int, int> >&)':
tickets.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(hg<0 || lw<0 || hg+lw!=diff.size())
      |                      ~~~~~^~~~~~~~~~~~~
#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...