Submission #1090004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090004		onlk97	Carnival Tickets (IOI20_tickets)	C++14	55 / 100	599 ms	114736 KiB

tickets

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

long long find_maximum(int k,vector <vector <int> > x){
    int n=x.size(),m=x[0].size();
    vector <vector <int> > op(n,vector <int>(m,-1));
    int chkmx=0;
    for (int i=0; i<n; i++) for (int j=0; j<m; j++) chkmx=max(chkmx,x[i][j]);
    long long ans=0;
    if (k==1){
        int idxmn[n],idxmx[n];
        for (int i=0; i<n; i++){
            idxmn[i]=min_element(x[i].begin(),x[i].end())-x[i].begin();
            idxmx[i]=max_element(x[i].begin(),x[i].end())-x[i].begin();
        }
        long long dp[n+1][n+1],bac[n+1][n+1];
        for (int i=0; i<=n; i++){
            for (int j=0; j<=n; j++) dp[i][j]=-1e18;
        }
        dp[0][0]=0;
        for (int i=0; i<n; i++){
            for (int j=0; j<=n/2; j++){
                if (dp[i][j]-x[i][idxmn[i]]>=dp[i+1][j]){
                    dp[i+1][j]=dp[i][j]-x[i][idxmn[i]];
                    bac[i+1][j]=0;
                }
                if (dp[i][j]+x[i][idxmx[i]]>=dp[i+1][j+1]){
                    dp[i+1][j+1]=dp[i][j]+x[i][idxmx[i]];
                    bac[i+1][j+1]=1;
                }
            }
        }
        ans=dp[n][n/2];
        int cur=n/2;
        for (int i=n; i>0; i--){
            if (bac[i][cur]){
                op[i-1][idxmx[i-1]]=0;
                cur--;
            } else {
                op[i-1][idxmn[i-1]]=0;
            }
        }
    } else if (chkmx<=1){
        int bal[n];
        for (int i=0; i<n; i++){
            bal[i]=0;
            for (int j=0; j<m; j++){
                if (!x[i][j]) bal[i]--;
                else bal[i]++;
            }
        }
        int fr[n],ba[n];
        for (int i=0; i<n; i++) fr[i]=0;
        for (int i=0; i<n; i++) ba[i]=m-1;
        for (int i=0; i<k; i++){
            vector <pair <int,int> > v;
            for (int j=0; j<n; j++) v.push_back({bal[j],j});
            sort(v.begin(),v.end());
            for (int j=0; j<n; j++){
                if (j<n/2){
                    op[v[j].second][fr[v[j].second]]=i;
                    if (!x[v[j].second][fr[v[j].second]]) bal[v[j].second]++;
                    else bal[v[j].second]--;
                    ans-=x[v[j].second][fr[v[j].second]];
                    fr[v[j].second]++;
                } else {
                    op[v[j].second][ba[v[j].second]]=i;
                    if (x[v[j].second][ba[v[j].second]]) bal[v[j].second]--;
                    else bal[v[j].second]++;
                    ans+=x[v[j].second][ba[v[j].second]];
                    ba[v[j].second]--;
                }
            }
        }
    } else if (k==m){
        vector <pair <long long,pair <int,int> > > v;
        for (int i=0; i<n; i++) for (int j=0; j<m; j++) v.push_back({x[i][j],{i,j}});
        sort(v.begin(),v.end());
        for (int i=0; i<n*m; i++){
            if (i<n*m/2) ans-=v[i].first;
            else ans+=v[i].first;
        }
        bool is[n][m];
        for (int i=0; i<n; i++) for (int j=0; j<m; j++) is[i][j]=0;
        for (int i=n*m/2; i<n*m; i++) is[v[i].second.first][v[i].second.second]=1;
        int idx=0;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (is[i][j]){
                    op[i][j]=idx;
                    idx++;
                    if (idx>=m) idx-=m;
                }
            }
        }
        bool hv[m];
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++) hv[j]=0;
            for (int j=0; j<m; j++) if (op[i][j]>=0) hv[op[i][j]]=1;
            int ptr=0;
            for (int j=0; j<m; j++){
                if (op[i][j]==-1){
                    while (hv[ptr]) ptr++;
                    op[i][j]=ptr;
                    ptr++;
                }
            }
        }
    }
    allocate_tickets(op);
    return ans;
}

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