Submission #433613

#	Time	Username	Problem	Language	Result	Execution time	Memory
433613		Mounir	Boat (APIO16_boat)	C++14	0 / 100	2083 ms	844 KiB

boat

#include <bits/stdc++.h>
#define chmax(x, v) x = max(x, v)
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;

const int N = 105, MOD = 1e9 + 7, INDEFINI = -1;


struct Inter {
	int deb, fin;
};

int dp[2][2 * N][N], sumDp[2][2 * N][N];
int taille[N];
int nBoats;
vector<Inter> inters;

map<pii, int> binome;

int expo(int val, int exposant){
	if (exposant == 0)
		return 1;
	if (exposant == 1)
		return val;
	int res = expo(val, exposant/2);
	res = (res * res)%MOD;
	if (exposant%2 == 1)
		res = (res * val)%MOD;
	return res;
}

int nFacons(int k, int n){
	pii situation = {k, n};
	if (k > n)
		return 0;
	if (k == n)
		return 1;

	//cout << "nf " << k << " " << n << endl;

	if (binome.count(situation) == 0){
		if (k == 1)
			binome[situation] = 1;
		else {
			binome[situation] = 1;
			for (int ind = n; ind > n - k; ++ind)
				binome[situation] = (binome[situation] * ind)%MOD;
			for (int ind = 2; ind <= k; ++ind)
				binome[situation] = (binome[situation] * expo(ind, MOD - 2))%MOD;
		}

	}
	//cout << "fini!\n";

	return binome[situation];
}

int getDp(int iBoat, int iPetit, int nMeme){
	if (iBoat == -1)
		return nFacons(nMeme, taille[iPetit]);
	if (iPetit < inters[iBoat].deb || iPetit >= inters[iBoat].fin)
		return 0;

	if (dp[iBoat%2][iPetit][nMeme] == INDEFINI){
		dp[iBoat%2][iPetit][nMeme] = 0;

		//Si on change d'intervalle

		if (iBoat != 0){
			for (int valAvant = 0; valAvant < iPetit; ++valAvant)
				dp[iBoat%2][iPetit][nMeme] = (dp[iBoat%2][iPetit][nMeme] + sumDp[(iBoat - 1)%2][valAvant][1])%MOD;
			dp[iBoat%2][iPetit][nMeme] = (dp[iBoat%2][iPetit][nMeme] * nFacons(nMeme, taille[iPetit]))%MOD;
			//cout << "calc " << iBoat << " " << iPetit << " " << nMeme << " " << nFacons(nMeme, taille[iPetit]);
			//Si on reste sur le même intervalle
			dp[iBoat%2][iPetit][nMeme] = (dp[iBoat%2][iPetit][nMeme] + sumDp[(iBoat - 1)%2][iPetit][nMeme + 1])%MOD;
		}
		//Si cetait le premier
		dp[iBoat%2][iPetit][nMeme] = (dp[iBoat%2][iPetit][nMeme] + getDp(-1, iPetit, nMeme));
	//	cout << "DP " << iBoat << " " << iPetit << " " << nMeme << " " << dp[iBoat][iPetit][nMeme] << endl;
	}
	return dp[iBoat%2][iPetit][nMeme];
}


signed main(){
	cin >> nBoats;
	vector<int> vals;
	inters.resize(nBoats);
	for (Inter& inter : inters){
		cin >> inter.deb >> inter.fin;
		inter.fin++; //Fin exclue
		vals.pb(inter.deb);
		vals.pb(inter.fin);
	}

	sort(all(vals));
	vector<int> t = {vals[0]};
	for (int ind = 1; ind < sz(vals); ++ind){
		if (vals[ind] != vals[ind - 1])
			t.pb(vals[ind]);
	}
	vals = t;
	//vals.pb(vals.back());

	map<int, int> compression;
	for (int ind = 0; ind < sz(vals); ++ind){
		compression[vals[ind]] = ind;
		if (ind != 0)
			taille[ind - 1] = vals[ind] - vals[ind - 1];
	}

	//int id = 0;
	for (Inter& inter : inters){
		inter.deb = compression[inter.deb];
		inter.fin = compression[inter.fin];
		//cout << "inter " << inter.deb << " " << inter.fin << endl;
	}

	for (int i = 0; i < nBoats; ++i)
		for (int j = 0; j < 2 * nBoats; ++j)
			for (int k = 0; k < nBoats; ++k)
				dp[i%2][j][k] = INDEFINI;

	int sum = 0;
	for (int i = 0; i < nBoats; ++i){
		for (int j = 0; j < sz(vals) - 1; ++j){
			for (int k = 0; k < nBoats; ++k){
				sumDp[i%2][j][k] = getDp(i, j, k);
				if (i != 0)
					sumDp[i%2][j][k] = (sumDp[i%2][j][k] + sumDp[(i - 1)%2][j][k])%MOD;
			}
			sum = (sum + getDp(i, j, 1))%MOD;
		}
	}
	
	cout << sum << endl;
	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42