Submission #109247

#	Time	Username	Problem	Language	Result	Execution time	Memory
109247		hugo_pm	Cake 3 (JOI19_cake3)	C++17	100 / 100	1717 ms	13688 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

typedef pair<int, ll> pil;

const int borne = 200*1005;
int nbPerles, nbVoulu;
struct Perle
{
	int couleur, taille, relCoul;
};
Perle perles[borne];
ll rep = -BIG;

// Début segtree

int posInSegtree[4*borne];
int stNbOn[4*borne];
ll stSom[4*borne];

int cl = 0, cr = -1;

void addElem(int posOp, int val, int coeff)
{
	int cur = posInSegtree[posOp];
	stNbOn[cur] += coeff;
	stSom[cur] += (ll)(coeff*val);
	while (cur > 1) {
		cur /= 2;
		stNbOn[cur] = stNbOn[2*cur] + stNbOn[2*cur+1];
		stSom[cur] = stSom[2*cur] + stSom[2*cur+1];
	}
}

void init(int nod, int leftNod, int rightNod)
{
	if (leftNod == rightNod) {
		posInSegtree[leftNod] = nod;
	} else {
		int midNod = (leftNod + rightNod) / 2;
		init(2*nod, leftNod, midNod);
		init(2*nod+1, midNod+1, rightNod);
	}
}
int opWalk = 0;
pil walk(int nod, int nbPrendre)
{
	opWalk++;
	if (stNbOn[nod] == 0 || nbPrendre == 0) {
		//cout << nod << " " << endl << flush;
		return {0,0};
	}
	if (stNbOn[nod] <= nbPrendre) {
		return {stNbOn[nod], stSom[nod]};
	}
	pil ret = walk(2*nod+1, nbPrendre); // D'abord marcher vers la droite
	//assert(ret.fi <= nbPrendre);
	nbPrendre -= ret.fi;
	pil oth = walk(2*nod, nbPrendre); // ensuite compléter avec la gauche
	//assert(oth.fi <= nbPrendre);
	ret.fi += oth.fi;
	ret.se += oth.se;
	return ret;
}

void upd(int iPerle, int coeff)
{
	addElem(perles[iPerle].relCoul, perles[iPerle].couleur, coeff);	
}	

int opSt = 0;
void ajusterSegtree(int newLeft, int newRight)
{
	while (cl > newLeft) { // Ajout
		--cl; ++opSt;
		upd(cl, 1);
	}
	while (cr < newRight) { // Ajout
		++cr; ++opSt;
		upd(cr, 1);
	}

	while (cl < newLeft) { // Suppression
		upd(cl, -1);
		++cl; ++opSt;
	}

	while (cr > newRight) { // Suppresion
		upd(cr, -1);
		--cr; ++opSt;
	}
	////assert(stNbOn[1] == cr-cl+1);
}


void calcDp(int caLeft, int caRight, int optLeft, int optRight)
{
	//cout << "## " << caLeft << " " << caRight << " " << optLeft << " " << optRight << endl << flush;
	if (caLeft > caRight) return;

	int caMid = min((caLeft + caRight) / 2, optRight-nbVoulu+1);
	if (caMid < caLeft) return;

	int debOpt = max(caMid+nbVoulu-1, optLeft);
	chmax(optRight, debOpt);

	ll sousRep = -BIG;

	int bestOpt = debOpt;

	form2(optTry, debOpt, optRight+1) {
		ajusterSegtree(caMid, optTry);
		pil ret = walk(1, nbVoulu);
		//cout << "###\n";
		//assert(ret.fi <= nbVoulu);

		if (ret.fi == nbVoulu) {
			ll nvRep = ret.se - 2*(perles[optTry].taille - perles[caMid].taille);
			//cout << caMid << " " << optTry << " : " << ret.fi << " " << ret.se << " -> " << nvRep << "\n";
			if (optTry == debOpt || nvRep > sousRep) {
				sousRep = nvRep;
				bestOpt = optTry;
			}
		}
	}
	chmax(rep, sousRep);

	calcDp(caLeft, caMid-1, optLeft, bestOpt);
	calcDp(caMid+1, caRight, bestOpt, optRight);
}

void solve()
{
	cin >> nbPerles >> nbVoulu;
	form(i, nbPerles) { cin >> perles[i].couleur >> perles[i].taille; }

	// Tri par couleur
	sort(perles, perles+nbPerles, [&] (Perle a, Perle b) { return tie(a.couleur, a.taille) < tie(b.couleur, b.taille); });
	// Détermine les relCoul
	form(i, nbPerles) perles[i].relCoul = i;

	// Tri par taille
	sort(perles, perles+nbPerles, [&] (Perle a, Perle b) { return tie(a.taille, a.couleur) < tie(b.taille, b.couleur); });
	//form(i, nbPerles) cout << i << ") " << perles[i].couleur << " " << perles[i].taille << "\n";

	init(1, 0, nbPerles-1);
	calcDp(0, nbPerles-1, 0, nbPerles-1);
	cout << rep << "\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76