Submission #1062638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062638		new_acc	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	789 ms	76372 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int N=2e3+10;
int t[N];
pair<int,int> r[N];
ll s1[N],s2[N];
bool vis[N][2];
ll find_maximum(int k, vector<vi> x) {
	int n=x.size();
	int m=x[0].size();
    vector<vi> ans=x;
    for(int i=0;i<n;i++){
        for(int i2=0;i2<m;i2++) ans[i][i2]=-1;
    }
    set<pair<ll,int>> dod,usu;
    ll res=0;
    for(int i=1;i<=n;i++){
        r[i]={0,m-1};         
        if(i>n/2){
            t[i]=k;
            for(int i2=1;i2<=k;i2++) res-=x[i-1][i2-1]; 
            usu.insert({x[i-1][k-1]+x[i-1][m-1],i});
            s1[i]=x[i-1][k-1]+x[i-1][m-1];
            vis[i][0]=1;
        }else{
            t[i]=0;
            for(int i2=1;i2<=k;i2++) res+=x[i-1][m-i2];
            dod.insert({-x[i-1][0]-x[i-1][m-k],i});
            s2[i]=-x[i-1][0]-x[i-1][m-k];
            vis[i][1]=1;
        }
    }  
    while(1){
        auto it=usu.end();
        it--; 
        auto it2=dod.end();
        it2--;
        auto v1=*it;
        auto v2=*it2;
        usu.erase(it),dod.erase(it2);
        if(v1.fi+v2.fi<=0) break;
        res+=v1.fi,res+=v2.fi;
        t[v1.se]--,t[v2.se]++;
        if(vis[v1.se][1]) dod.erase({s2[v1.se],v1.se});
        if(vis[v2.se][0]) usu.erase({s1[v2.se],v2.se});
        vis[v1.se][0]=0,vis[v2.se][1]=0;
        vis[v1.se][1]=1,vis[v2.se][0]=1;
        s2[v1.se]=-v1.fi,s1[v2.se]=-v2.fi;
        dod.insert({s2[v1.se],v1.se}),usu.insert({s1[v2.se],v2.se});
        if(t[v1.se]){
            vis[v1.se][0]=1;
            s1[v1.se]=x[v1.se-1][t[v1.se]-1]+x[v1.se-1][m-(k-t[v1.se])-1];
            usu.insert({s1[v1.se],v1.se});
        } 
        if(t[v2.se]<k){
            vis[v2.se][1]=1;
            s2[v2.se]=-x[v2.se-1][t[v2.se]]-x[v2.se-1][m-(k-t[v2.se])];
            dod.insert({s2[v2.se],v2.se});
        }
    }
    for(int i=1;i<=k;i++){
        int il=0;
        vi zos;
        for(int i2=1;i2<=n;i2++){
            if(t[i2]==0){
                il++;
                ans[i2-1][r[i2].se--]=i-1;
                continue;
            }
            if(t[i2]==k-i+1){
                t[i2]--,il--;
                ans[i2-1][r[i2].fi++]=i-1;
                continue;
            }
            zos.push_back(i2);
        }
        for(auto u:zos){
            if(il>0){
                t[u]--,il--;
                ans[u-1][r[u].fi++]=i-1;
            }else{
                il++;
                ans[u-1][r[u].se--]=i-1;
            }
        }
    }
	allocate_tickets(ans);
	return res;
}

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