Submission #791061

#	Time	Username	Problem	Language	Result	Execution time	Memory
791061		alexander707070	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	2 ms	852 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#define MAXN 1507
using namespace std;

const long long inf=1e15;

int n,m,sol[MAXN],k,rest[MAXN],br,maxs,ind[MAXN],cnt0,cnt1,ans;
pair<int,int> s[MAXN][MAXN];
vector<int> curr;
vector< vector<int> > res;
int used[MAXN],tim;
vector< pair<int,int> > all;

long long find_maximum(int K,vector< vector<int> > x){
    n=int(x.size()); m=int(x[0].size()); k=K;
    res.resize(n);

    for(int i=0;i<n;i++){
        res[i].resize(m); ind[i]=i;
        for(int f=0;f<m;f++){
            s[i][f]={x[i][f],f};
            res[i][f]=-1;

            all.push_back({x[i][f],i});
        }
        sort(s[i],s[i]+m);
    }

    sort(all.begin(),all.end());

    for(int i=0;i<n*m/2;i++){
        sol[all[i].second]++;
        ans-=all[i].first;
    }
    for(int i=n*m/2;i<n*m;i++){
        rest[all[i].second]++;
        ans+=all[i].first;
    }

    for(int i=0;i<k;i++){
        br=n/2; tim++;
        cnt0=cnt1=0;

        for(int f=0;f<n;f++){
            if(sol[f]>0)cnt0++;
            if(rest[f]>0)cnt1++;
        }

        if((cnt0>=n/2 and cnt1>=n/2) or cnt0<n/2){
            for(int f=0;f<n/2;f++){
                maxs=n;
                for(int w=0;w<n;w++){
                    if(sol[w]>sol[maxs] and used[w]!=tim)maxs=w;
                }

                if(sol[maxs]==0)break;

                res[maxs][s[maxs][sol[maxs]-1].second]=i;
                sol[maxs]--; used[maxs]=tim; br--;
            }

            for(int f=0;f<n;f++){
                if(used[f]!=tim){
                    res[f][s[f][m-rest[f]].second]=i; rest[f]--;
                }
            }
        }else{
            for(int f=0;f<n/2;f++){
                maxs=n;
                for(int w=0;w<n;w++){
                    if(rest[w]>rest[maxs] and used[w]!=tim)maxs=w;
                }

                if(rest[maxs]==0)break;

                res[maxs][s[maxs][m-rest[maxs]].second]=i;
                rest[maxs]--; used[maxs]=tim; br--;
            }

            for(int f=0;f<n;f++){
                if(used[f]!=tim){
                    res[f][s[f][sol[f]-1].second]=i; sol[f]--;
                }
            }
        }
    }

    allocate_tickets(res);
    return ans;
}


/*
int main(){
    cout<<find_maximum(2, {{0, 2, 5},{1, 1, 3}})<<"\n";
}
*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10