Submission #300621

#	Time	Username	Problem	Language	Result	Execution time	Memory
300621		MarcoMeijer	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	2 ms	416 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 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) {
        int 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 dp
    dp.assign(n+1,vll(totBig+1, -1e18));
    dpOpt.assign(n+1,vll(totBig+1, -1));
    dp[0][0] = 0;
    REP(i,1,n) RE(j,totBig+1) {
        RE(I,min(k+1,j+1)) {
            ll ndp = dp[i-1][j-I] + cost[i-1][I];
            if(ndp > dp[i][j]) {
                dp[i][j] = ndp;
                dpOpt[i][j] = I;
            }
        }
    }
    searchDp(n,totBig);

    // 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(i,n) best.pb({big[i], i});
        sort(all(best), greater<ii>());
        RE(j,n/2) {
            int x = best[j].se;
            ans += X[x][ticketBig[x]];
            big[ticketBig[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: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10