| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 419905 | mosiashvililuka | Carnival Tickets (IOI20_tickets) | C++14 | 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 "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1509][1509],k,jm,pi,ee,qi,tes,t;
pair <long long, long long> q[3000009];
pair <long long, pair <long long, long long> > p[3000009];
//bool bo[1509][1509];
long long bo[1509];
vector <vector <long long> > ans;
/*void allocate_tickets(vector <vector <long long> > XX){
long long qw=0,we=0;
for(qw=0; qw<a; qw++){
for(we=0; we<b; we++){
cout<<XX[qw][we]<<" ";
}
cout<<endl;
}
}*/
long long find_maximum(long long K, vector<vector<long long> > Xx) {
k=K;
a=Xx.size();b=Xx[0].size();
ans.resize(a);
for(i=0; i<a; i++){
ans[i].resize(b);
for(j=0; j<b; j++){
f[i][j]=Xx[i][j];
}
}
jm=0;
for(i=0; i<a; i++){
for(j=0; j<k; j++){
jm-=f[i][j];
//bo[i][j]=1;
bo[i]++;
ii=i;jj=b-(k-j);
pi++;
p[pi].first=-(f[i][jj]+f[i][j]);
p[pi].second=make_pair(i,jj);
}
}
sort(p+1,p+pi+1);
for(i=1; i<=pi; i++){
p[i].first=-p[i].first;
}
ee=a*k/2;
for(e=1; e<=ee; e++){
i=p[e].second.first;j=p[e].second.second;
jm+=p[e].first;
ii=i;jj=b-(k-j);
//bo[i][j]=1;bo[i][jj]=0;
bo[i]--;
}
/*for(i=0; i<a; i++){
cout<<bo[i]<<" K ";
}
cout<<endl;*/
for(i=0; i<a; i++){
for(j=0; j<b; j++){
ans[i][j]=-1;
}
}
t=0;
while(k>0){
qi=-1;
for(i=0; i<a; i++){
qi++;
q[qi].first=bo[i];
q[qi].second=i;
}
sort(q,q+qi+1);
for(ii=0; ii<a/2; ii++){
i=q[ii].second;
j=b-(k-bo[i]);
//cout<<i<<" "<<j<<" + "<<t<<endl;
ans[i][j]=t;
}
for(ii=a/2; ii<a; ii++){
i=q[ii].second;
j=bo[i]-1;
//cout<<i<<" "<<j<<" - "<<t<<endl;
ans[i][j]=t;
bo[i]--;
}
k--;t++;
}
allocate_tickets(ans);
return jm;
}
/*int main(){
vector <vector <long long> > qw;
cin>>a>>b>>k;
qw.resize(a);
for(i=0; i<a; i++){
for(j=0; j<b; j++){
cin>>c;
qw[i].push_back(c);
}
}
cout<<find_maximum(k,qw);
return 0;
}*/