Submission #305110

#	Time	Username	Problem	Language	Result	Execution time	Memory
305110		ocarima	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1010 ms	119484 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;
vi todos;
vector<vector<int> > respuesta;
pii dp[MAX_N][MAX_N];
pii tickets[MAX_N][MAX_N];
int usados[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){
        rep(j, 0, m - 1){
            tickets[i][j] = {x[i][j], j};
            todos.push_back(x[i][j]);
        }
        sort(tickets[i], tickets[i] + m);
	}
    sort(todos.begin(), todos.end());
    mediana = todos[(n * m) >> 1];


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

    rep(i, 1, n - 1){
        rep(j, 1, n / 2){
            ch = dp[i - 1][j - 1].maximo + mediana - tickets[i][0].color;
            gr = dp[i - 1][j].maximo + tickets[i][m - 1].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) usados[a] = tickets[a][m - 1].pos;
        else {
            usados[a] = tickets[a][0].pos;
            b--;
        }
        a--;
    }

    rep(i, 0, n - 1){
        debug(usados[i]);
        vector<int> bolsa(m);
        rep(j, 0, m - 1){
            if (j == usados[i]) bolsa[j] = 0;
            else bolsa[j] = -1;
        }
        respuesta.push_back(bolsa);
	}

	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