Submission #300642

#	Time	Username	Problem	Language	Result	Execution time	Memory
300642		MarcoMeijer	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1184 ms	80880 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ll> lll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=1505;

int n, k, m;
vvi X;
vvi answer;
vvll dp;
vvll dpOpt;
ll cost[MX][MX];
int big[MX];
int ticketBig[MX], ticketSmall[MX];

void searchDp(int x, int y) {
    if(x == 0) return;
    int opt = dpOpt[x][y];
    big[x-1] = opt;
    searchDp(x-1, y-opt);
}

ll find_maximum(int _k, vvi _x) {
    k = _k; X = _x;
    n = X.size();
    m = X[0].size();
    int totBig = (n/2)*k;

    // fill cost
    RE(i,n) {
        ll sm = 0;
        RE(j,k) sm -= X[i][j];
        RE(j,k+1) {
            cost[i][j] = sm;
            if(j == k) break;
            sm += X[i][k-1-j];
            sm += X[i][m-1-j];
        }
    }

    // fill big
    priority_queue<lll> pq;
    RE(i,n) big[i] = 0;
    RE(i,n) pq.push({cost[i][big[i]+1] - cost[i][big[i]], i});
    RE(i,totBig) {
        int x = pq.top().se; pq.pop();
        big[x]++;
        if(big[x] != k) pq.push({cost[x][big[x]+1] - cost[x][big[x]], x});
    }

    // create answer
    ll ans = 0;
    answer.assign(n,vi(m,-1));
    RE(i,n) ticketBig[i]=m-1, ticketSmall[i]=0;
    RE(i,k) {
        vii best;
        RE(j,n) best.pb({big[j], j});
        sort(all(best), greater<ii>());
        RE(j,n/2) {
            int x = best[j].se;
            ans += X[x][ticketBig[x]];
            big[x]--;
            answer[x][ticketBig[x]--] = i;
        }
        RE(j,n/2) {
            int x = best[j+n/2].se;
            ans -= X[x][ticketSmall[x]];
            answer[x][ticketSmall[x]++] = i;
        }
    }

    allocate_tickets(answer);
    return ans;
}

• 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