Submission #730868

#	Time	Username	Problem	Language	Result	Execution time	Memory
730868		beaconmc	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1785 ms	212856 KiB

tickets

#include "tickets.h"
 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;
 
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
 
ll dp[1501][1501];
ll nextt[1501][1501];
ll maxi = -1;
ll mini = -1;

 
long long find_maximum(int k, vector<vector<int>> x) {
 
	ll n = x.size();
	ll m = x[0].size();
 
	vector<vector<int>> assigns;  
	 FOR(i,0,n){
    	vector<int> temp;
    	FOR(j,0,m) temp.push_back(-1);
    	assigns.push_back(temp);
    }
 
	vector<vector<ll>> orders;
	vector<vector<ll>> minmax;
	FOR(i,0,n){
		minmax.push_back({k,0});
	}
	FOR(i,0,n){

		FOR(j,m-k,m){
			orders.push_back({x[i][j]+x[i][j-(m-k)], i});
		}
	}


	sort(orders.begin(), orders.end());
	reverse(orders.begin(), orders.end());



	ll top = 0;
	FOR(i,0,orders.size()){
		ll ind = orders[i][1];
		//cout << ind <<" " << plus << endl;
		if (minmax[ind][0]>0 && top < n*k/2){
			minmax[ind][1] += 1;
			minmax[ind][0] -= 1;
			top += 1;
		}
	}

 
	vector<vector<ll>> q;
 
	for (auto&i : minmax) q.push_back(i);
	FOR(i,0,n) q[i].push_back(i);
	ll ans = 0;
 
	ll cur = 0;
 
	while (q[0][0] + q[0][1] > 0){
		sort(q.begin(), q.end());
		reverse(q.begin(), q.end());

 
 
		FOR(i,0,n/2){
			assigns[q[i][2]][q[i][0]-1] = cur;
			q[i][0] -= 1;
			ans -= x[q[i][2]][q[i][0]];
		}
		FOR(i,n/2,n){
 
			assigns[q[i][2]][m-q[i][1]] = cur;
			ans += x[q[i][2]][m-q[i][1]];
			q[i][1] -= 1;
		}
 
		cur++;
	}
 
 
	allocate_tickets(assigns);

	return ans;
 
 
 
 
 
 
}
 

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:11:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   53 |  FOR(i,0,orders.size()){
      |      ~~~~~~~~~~~~~~~~~             
tickets.cpp:53:2: note: in expansion of macro 'FOR'
   53 |  FOR(i,0,orders.size()){
      |  ^~~

• 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