Submission #832190

#	Time	Username	Problem	Language	Result	Execution time	Memory
832190		penguinman	Carnival Tickets (IOI20_tickets)	C++17	41 / 100	802 ms	147316 KiB

tickets

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

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	ll N = x.size();
	ll M = x[0].size();
	if(M == k){
		vector<std::tuple<ll,ll,ll>> data;
		rep(i,0,N){
			rep(j,0,M) data.pb(mtp(x[i][j],i,j));
		}
		sort(all(data));
		ll ans = 0;
		ll mid = N*M/2;
		vii left(N), right(N);
		rep(i,0,mid){
			ll val, I,J; std::tie(val, I,J) = data[i];
			left[I].pb(J);
			ans -= val;
		}
		rep(i,mid,N*M){
			ll val, I,J; std::tie(val, I,J) = data[i];
			right[I].pb(J);
			ans += val;
		}
		vector<vector<int>> allocate(N,vector<int>(M,-1));
		vector<pii> cnt(M);
		rep(i,0,M) cnt[i] = mp(0,i);
		rep(i,0,N){
			sort(all(cnt));
			ll idx = 0;
			for(auto el: left[i]){
				allocate[i][el] = cnt[idx].second;
				cnt[idx].first++;
				idx++;
			}
			for(auto el: right[i]){
				allocate[i][el] = cnt[idx].second;
				cnt[idx].first--;
				idx++;
			}
		}
		allocate_tickets(allocate);
		return ans;
	}
	if(N <= 300 && M <= 300){
		vector<vector<int>> allocate(N,vector<int>(M,-1));
		ll ans = 0;
		rep(t,0,k){
			vector<std::tuple<ll,ll,ll>> data;
			rep(i,0,N){
				rep(j,0,M){
					if(allocate[i][j] == -1) data.pb(mtp(x[i][j],i,j));
				}
			}
			sort(all(data));
			ll mid = data.size()/2;
			vi left(N, -1), right(N, -1);
			rep(i,0,mid){
				ll val, I,J; std::tie(val, I,J) = data[i];
				if(left[I] == -1) left[I] = J;
			}
			per(i,data.size()-1, mid){
				ll val, I,J; std::tie(val, I,J) = data[i];
				if(right[I] == -1) right[I] = J;
			}
			ll L = 0, R = 0;
			vector<pii> data2;
			rep(i,0,N){
				if(left[i] == -1){
					R++;
					allocate[i][right[i]] = t;
					ans += x[i][right[i]];
				}
				else if(right[i] == -1){
					L++;
					allocate[i][left[i]] = t;
					ans -= x[i][left[i]];
				}
				else{
					data2.pb(mp(x[i][right[i]]+x[i][left[i]], i));
					ans -= x[i][left[i]];
				}
			}
			sort(all(data2));
			L = N/2-L;
			R = N/2-R;
			rep(i,0,L){
				auto el = data2[i];
				allocate[el.second][left[el.second]] = t;
			}
			rep(i,L,L+R){
				auto el = data2[i];
				allocate[el.second][right[el.second]] = t;
				ans += el.first;
			}
		}
		allocate_tickets(allocate);
		return ans;
	}
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:120:1: warning: control reaches end of non-void function [-Wreturn-type]
  120 | }
      | ^

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