Submission #1144779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144779		PagodePaiva	Carnival Tickets (IOI20_tickets)	C++20	0 / 100	132 ms	13336 KiB

tickets

#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
#define ll long long

using namespace std;

const long long N = 85;
vector <vector <int>> x;
long long n, m, k;
long long l[N], r[N];
long long cnt[N];
long long ans[N][N];
long long dp[N][N*N];
long long best[N][N*N];
long long pref[N][N];
vector <vector <int>> answer;

/*
X <= (N/2)*K
dp[i][j] = estou na linha i e quero pegar j bons
O(n*n*k*m)
*/

long long query(long long linha, long long l, long long r){
	if(r < l) return 0;
	if(l == 0) return pref[linha][r];
	return pref[linha][r]-pref[linha][l-1];
}

void solve(){
	memset(ans, -1, sizeof ans);
	vector<array <long long, 3>> valores;
	for(long long i = 0;i < n;i++){
		cnt[i] = 0;
		for(long long j = 0;j <= l[i];j++){
			valores.push_back({x[i][j], i, j});
		}
		for(long long j = r[i];j < m;j++){
			valores.push_back({x[i][j], i, j});
		}
	}	
	sort(valores.begin(), valores.end());
	for(long long i = 0;i < (n/2)*k;i++){
		cnt[valores[i][1]]++;
	}
	long long res = 0;
	long long turno = 0;
	for(long long i = 0;i < n;i++){
		r[i] = m-1;
		l[i] = 0;
	}
	for(long long i = 0;i < k;i++){
		vector <pair <long long, long long>> contadores;
		for(long long i = 0;i < n;i++){
			contadores.push_back({cnt[i], i});
		}
		sort(contadores.begin(), contadores.end());
		for(long long i = 0;i < n/2;i++){
			swap(contadores[i].first, contadores[i].second);
			ans[contadores[i].first][r[contadores[i].first]] = turno;
			res += x[contadores[i].first][r[contadores[i].first]];
			r[contadores[i].first]--;
		}
		for(long long i = n/2;i < n;i++){
			swap(contadores[i].first, contadores[i].second);
			ans[contadores[i].first][l[contadores[i].first]] = turno;
			res -= x[contadores[i].first][l[contadores[i].first]];
			l[contadores[i].first]++;
			cnt[contadores[i].first]--;
		}
		turno++;
	}
	for(long long i = 0;i < n;i++){
		vector <int> aux;
		for(long long j = 0;j < m;j++){
			aux.push_back(ans[i][j]);
		}
		answer.push_back(aux);
	}
	allocate_tickets(answer);
}

int custo(int i, int t){
	return - query(i, 0, t-1) + query(i, m-(k-t), m-1);
}

void calc(int linha, int l, int r, int tl, int tr){
	if(l > r) return;
	int mid = (l+r)/2;
	dp[linha][mid] = -1e14;
	best[linha][mid] = -1;
	for(int i = max((long long) tl, mid-k);i <= min(tr, mid);i++){
		if(dp[linha][mid] < dp[linha-1][i] + custo(linha, mid-i)){
			dp[linha][mid] = dp[linha-1][i] + custo(linha, mid-i);
			best[linha][mid] = mid-i;
		}
	}
	calc(linha, l, mid-1, tl, mid-best[linha][mid]);
	calc(linha, mid+1, r, mid-best[linha][mid], tr);
	return;
}

long long find_maximum(int kk, std::vector<std::vector<int>> xx) {
	x = xx;
	memset(ans, -1, sizeof ans);
	n = x.size();
	m = x[0].size();
	k = kk;
	vector<array <long long, 3>> valores;
	for(long long i = 0;i < n;i++){
		for(long long j = 0;j < m;j++){
			valores.push_back({x[i][j], i, j});
			pref[i+1][j] = (j == 0 ? 0 : pref[i+1][j-1]) + x[i][j];
		}
	}	
	sort(valores.begin(), valores.end());
	for(long long i = 0;i < (n/2)*m;i++){
		cnt[valores[i][1]+1]++;
	}
	dp[0][0] = 0;
	for(long long i = 1;i <= n*k;i++){
		dp[0][i] = -1e17;
	}
	for(int i = 1;i <= n;i++){
		calc(i, 0, (n/2)*k, 0, (n/2)*k);
	}
	long long nn = n, qtd = (n/2)*k;
	while(nn > 0){
		long long v = best[nn][qtd];
		if(v == -1) exit(0);
		l[nn-1] = v-1;
		r[nn-1] = m-(k-v);
		qtd -= v;
		nn--;
	}
	solve();
	return dp[n][(n/2)*k];
}

• 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