Submission #307209

#	Time	Username	Problem	Language	Result	Execution time	Memory
307209		Ruxandra985	Carnival Tickets (IOI20_tickets)	C++14	0 / 100	75 ms	2552 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];

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];

	}

	int can = 1;

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


        maxi = -1000000000000000000;
        poz = -1;

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

            if (prefix[i] && maxi < sol + x[i][prefix[i]] + x[i][sufix[i] - 1]){

                maxi = sol + x[i][prefix[i]] + x[i][sufix[i] - 1];


                poz = i;

            }

        }

        sol = maxi;
        prefix[poz]--;
        sufix[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:16:29: warning: unused variable 'take' [-Wunused-variable]
   16 |  int n = x.size() , i , j , take , l , r , poz , st , dr;
      |                             ^~~~
tickets.cpp:35:6: warning: unused variable 'can' [-Wunused-variable]
   35 |  int can = 1;
      |      ^~~

• 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