Submission #307216

#	Time	Username	Problem	Language	Result	Execution time	Memory
307216		Ruxandra985	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	930 ms	54648 KiB

tickets

#include <bits/stdc++.h>
#include "tickets.h"
#define DIMN 1510
#define MLD 1000000000

using namespace std;


long long spl[DIMN][DIMN] , spr[DIMN][DIMN];
int prefix[DIMN] , sufix[DIMN];
int f[DIMN];

priority_queue<pair <long long , int> > h;

vector <long long> dp[DIMN] , tt[DIMN];

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size() , i , j , take , l , r , poz , st , dr;
	int m = x[0].size();
	long long sol = 0 , maxi;
	vector<vector<int>> answer;
	for (i = 0; i < n; i++) {
		vector<int> row;
		row.resize(m , -1);
		answer.push_back(row);
		sufix[i] = m;
		prefix[i] = k - 1;
	}

	for (i = 0 ; i < n ; i++){

        for (j = 0 ; j < k ; j++)
            sol -= x[i][j];

	}


	for (i = 0 ; i < n ; i++){

        h.push(make_pair(x[i][prefix[i]] + x[i][sufix[i] - 1] , i));

    }

	for (j = 1 ; j <= n * k / 2 ; j++){


        maxi = -1000000000000000000;
        poz = -1;

        maxi = sol + h.top().first;
        poz = h.top().second;

        h.pop();

        sol = maxi;
        prefix[poz]--;
        sufix[poz]--;

        if (prefix[poz] >= 0){

            h.push(make_pair(x[poz][prefix[poz]] + x[poz][sufix[poz] - 1] , poz));

        }

	}



	i = n;
	st = 0;

	while (i){

        l = prefix[i - 1] + 1;

        for (r = 0 ; r < l ; r++){
            answer[i - 1][r] = st;
            st = (st + 1) % k;
        }

        dr = st;

        for (r = 0 ; r < k - l ; r++){
            answer[i - 1][m - 1 - r] = dr;
            dr = (dr + 1) % k;
        }

        i--;

    }

	allocate_tickets(answer);
	return sol;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:18:29: warning: unused variable 'take' [-Wunused-variable]
   18 |  int n = x.size() , i , j , take , l , r , poz , st , dr;
      |                             ^~~~

• 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