| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1050304 | Huseyn123 | Carnival Tickets (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std;
typedef long long ll;
ll find_maximum(ll k, vector<vector<int>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<int>> answer;
ll res=0;
if(m==1){
vector<ll> a;
for(ll i=0;i<n;i++){
a.pb(x[i][0]);
}
sort(a.begin(),a.end());
for(ll i=0;i<n;i++){
res+=abs(a[i]-a[n/2]);
}
for(ll i=0;i<n;i++){
answer.pb({0});
}
}
else if(k==1){
for(ll i=0;i<n;i++){
vector<int> d;
for(ll j=0;j<m;j++){
d.pb(-1);
}
answer.pb(d);
}
res=-1;
ll ind=0;
ll l[n],f[n];
vector<array<ll,3>> c;
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
c.pb({x[i][j],i,j});
}
l[i]=x[i][m-1];
f[i]=x[i][0];
}
sort(c.begin(),c.end());
set<pair<ll,ll>> s1,s2;
ll cnt=0;
ll sum1=0,sum2=0,sum3=0;
ll sz=(ll)c.size();
for(ll i=0;i<n;i++){
sum3+=l[i];
}
for(ll i=0;i<sz;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==m-1){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
sum2-=p.first;
}
else{
s2.erase(p);
}
}
ll res1=0;
if((ll)s1.size()==n/2-cnt){
ll sum=sum2;
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
if((ll)s2.size()!=0){
sum-=p.first;
p=*(--s2.end());
sum+=p.first;
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
else{
sum3-=l[c[i][1]];
res1=sum3-(n-cnt-1)*c[i][0]+2*c[i][0]*(n/2-cnt)+sum+cnt*c[i][0]-sum1;
sum3+=l[c[i][1]];
}
}
if(c[i][2]==0){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
sum2+=nw.first;
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
sum2-=p.first;
sum2+=nw.first;
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==m-1){
cnt++;
sum1+=f[c[i][1]];
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
sum2-=h.first;
}
sum3-=l[c[i][1]];
}
if(res1>res){
res=res1;
ind=i;
}
}
cnt=0;
s1.clear();
s2.clear();
for(ll i=0;i<=ind;i++){
if(n/2-cnt<0){
break;
}
if(c[i][2]==m-1){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if(s1.find(p)!=s1.end()){
s1.erase(p);
}
else{
s2.erase(p);
}
}
if(i==ind){
pair<ll,ll> p={-l[c[i][1]]-f[c[i][1]],c[i][1]};
for(auto x:s1){
if(x.second!=c[i][1]){
answer[x.second][0]=0;
}
}
if(s1.find(p)!=s1.end()){
if((ll)s2.size()==0){
continue;
}
p=*(--s2.end());
answer[p.second][0]=0;
}
for(ll j=0;j<n;j++){
if(j==c[i][1]){
answer[c[i][1]][c[i][2]]=0;
continue;
}
if(answer[j][0]==-1 && answer[j][m-1]==-1){
answer[j][m-1]=0;
}
}
break;
}
if(c[i][2]==0){
pair<ll,ll> p=*(s1.begin());
pair<ll,ll> nw={-l[c[i][1]]-f[c[i][1]],c[i][1]};
if((ll)s1.size()<n/2-cnt){
s1.insert(nw);
}
else{
if(nw.first>p.first){
s1.erase(p);
s1.insert(nw);
s2.insert(p);
}
else{
s2.insert(nw);
}
}
}
if(c[i][2]==m-1){
answer[c[i][1]][0]=0;
cnt++;
if((ll)s1.size()>n/2-cnt){
pair<ll,ll> h=*(s1.begin());
s1.erase(h);
s2.insert(h);
}
}
}
}
allocate_tickets(answer);
return res;
}