Submission #1215991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215991		cpdreamer	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	861 ms	63368 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
typedef long long ll;
const ll MOD = (ll)1e9+7;
#define P pair
#define S second
#define F first
#define pb push_back
#define V vector
#define all(v) v.begin(), v.end()
long long find_maximum(int k, std::vector<std::vector<int>> x) {
    int n=(int)x.size();
    int m=(int)x[0].size();
    int h=n/2;
    V<V<int>>vp(n,V<int>(m));
    V<int>left(n),right(n);
    ll a=0;
    for (int i=0;i<n;i++) {
        if (i<h) {
            for (int j=0;j<m;j++) {
                vp[i][j]=-1;
            }
            left[i]=-1;
            right[i]=m-k;
            for (int j=m-1;j>=m-k;j--) {
                a+=x[i][j];
                vp[i][j]=1;
            }
        }
        else {
            for (int j=0;j<m;j++) {
                vp[i][j]=-1;
            }
            right[i]=m;
            left[i]=k-1;
            for (int j=0;j<=k-1;j++) {
                a-=x[i][j];
                vp[i][j]=0;
            }
        }
    }
    multiset<P<int,int>>s1,s2;
    for (int i=0;i<n;i++) {
        if (right[i]!=m) {
            s1.insert({-x[i][right[i]]-x[i][left[i]+1],i});
        }
        if (left[i]!=-1) {
            s2.insert({x[i][left[i]]+x[i][right[i]-1],i});
        }
    }
    while (true) {
        V<ll>v(2,-1e17);
        V<int>id(2,-1);
        v[0]=prev(s1.end())->F;
        v[1]=prev(s2.end())->F;
        id[0]=prev(s1.end())->S;
        id[1]=prev(s2.end())->S;
        s1.erase(prev(s1.end()));
        s2.erase(prev(s2.end()));
        auto it=s2.find({x[id[0]][left[id[0]]]+x[id[0]][right[id[0]]-1],id[0]});
        if (it!=s2.end()) {
            s2.erase(it);
        }
        it=s1.find({-x[id[1]][right[id[1]]]-x[id[1]][left[id[1]]+1],id[1]});
        if (it!=s1.end()) {
            s1.erase(it);
        }
        if (v[0]+v[1]<=0) {
            break;
        }
        a+=v[0]+v[1];
        vp[id[0]][right[id[0]]]=-1;
        vp[id[0]][left[id[0]]+1]=0;
        vp[id[1]][left[id[1]]]=-1;
        vp[id[1]][right[id[1]]-1]=1;
        left[id[0]]++;
        right[id[0]]++;
        left[id[1]]--;
        right[id[1]]--;
        for (int j=0;j<2;j++) {
            int i=id[j];
            if (right[i]!=m) {
                s1.insert({-x[i][right[i]]-x[i][left[i]+1],i});
            }
            if (left[i]!=-1) {
                s2.insert({x[i][left[i]]+x[i][right[i]-1],i});
            }
        }
    }
    V<int>l;
    for (int i=0;i<h;i++) {
        for (int j=0;j<k;j++) {
            l.pb(j);
        }
    }
    V<V<int>>ans(n,V<int>(m,-1));
    int id=0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (vp[i][j]==0) {
                ans[i][j]=l[id];
                id++;
            }
        }
    }
    for (int i=0;i<n;i++) {
        set<int>st;
        for (int j=0;j<k;j++) {
            st.insert(j);
        }
        for (int j=0;j<m;j++) {
            if (vp[i][j]==0) {
                st.erase(ans[i][j]);
            }
        }
        for (int j=0;j<m;j++) {
            if (vp[i][j]==1) {
                ans[i][j]=*st.begin();
                st.erase(st.begin());
            }
        }
    }
    allocate_tickets(ans);
    return a;
}

• 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