Submission #305564

#	Time	Username	Problem	Language	Result	Execution time	Memory
305564		ocarima	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1012 ms	119228 KiB

tickets

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

using namespace std;

#define vi vector<int>
#define lli long long int
#define pii pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define debugsl(x) cerr << #x << " = " << x << ", "
#define debug(x) debugsl(x) << endl

#define MAX_N 1502
#define color first
#define pos second
#define maximo first
#define tipo second
#define chico 0
#define grande 1

lli suma;
lli mediana, gr, ch, a, b, offset;
vi todos;
vector<vector<int> > respuesta;
pii dp[MAX_N][MAX_N];
pii tickets[MAX_N][MAX_N];
int izq[MAX_N], der[MAX_N];


long long find_maximum(int k, vector<vector<int> > x) {
	int n = x.size();
	int m = x[0].size();

	rep(i, 0, n - 1){
        vector<int> bolsa(m);
        rep(j, 0, m - 1){
            tickets[i][j] = {x[i][j], j};
            todos.push_back(x[i][j]);
            bolsa[j] = -1;
        }
        sort(tickets[i], tickets[i] + m);
        izq[i] = 0;
        der[i] = m - 1;
        respuesta.push_back(bolsa);
	}
    sort(todos.begin(), todos.end());
    mediana = todos[((n * m) >> 1) - 1];
    if (mediana == todos[n * m - 1]) offset = 1;

    rep(ronda, 0, k - 1){
        dp[0][0] = {abs(tickets[0][der[0]].color - mediana), grande};
        dp[0][1] = {abs(mediana - tickets[0][izq[0]].color), chico};
        rep(i, 1, n - 1) dp[i][0] = {dp[i - 1][0].maximo + abs(tickets[i][der[i]].color - mediana), grande};

        rep(i, 1, n - 1){
            rep(j, 1, n / 2){
                ch = dp[i - 1][j - 1].maximo + abs(mediana - tickets[i][izq[i]].color);
                gr = dp[i - 1][j].maximo + abs(tickets[i][der[i]].color - mediana);

                if (ch <= gr) dp[i][j] = {gr, grande};
                else dp[i][j] = {ch, chico};
            }
        }

        suma += dp[n - 1][n / 2].maximo;
        a = n - 1;
        b = n / 2;
        while (a >= 0){
            if (dp[a][b].tipo == grande){
                respuesta[a][tickets[a][der[a]].pos] = ronda;
                der[a]--;
            }
            else {
                respuesta[a][tickets[a][izq[a]].pos] = ronda;
                izq[a]++;
                b--;
            }
            a--;
        }
    }

	allocate_tickets(respuesta);
	return suma;
}

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