Submission #1215978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215978		cpdreamer	Carnival Tickets (IOI20_tickets)	C++17	76 / 100	3094 ms	62268 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;
            }
        }
    }
    while (true) {
        V<ll>v(2,-1e17);
        V<int>id(2,-1);
        for (int i=0;i<n;i++) {
            if (right[i]!=m) {
                if (-x[i][right[i]]-x[i][left[i]+1]>v[0]) {
                    v[0]=-x[i][right[i]]-x[i][left[i]+1];
                    id[0]=i;
                }
            }
            if (left[i]!=-1) {
                if (x[i][left[i]]+x[i][right[i]-1]>v[1]) {
                    v[1]=x[i][left[i]]+x[i][right[i]-1];
                    id[1]=i;
                }
            }
        }
        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]]--;
    }
    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: 0 / 14
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23
• Subtask 7: 0 / 10