oj.uz

Submission #433603

# Submission time Handle Problem Language Result Execution time Memory
433603 2021-06-20T08:15:00 Z Mounir Boat (APIO16_boat) C++14
0 / 100
 2000 ms 524292 KB 
#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 = 505, MOD = 1e9 + 7, INDEFINI = -1;


struct Inter {
	int deb, fin;
};

int dp[N][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][iPetit][nMeme] == INDEFINI){
		dp[iBoat][iPetit][nMeme] = 0;

		//Si on change d'intervalle
		for (int avant = 0; avant < iBoat; ++avant)
			for (int valAvant = 0; valAvant < iPetit; ++valAvant)
				dp[iBoat][iPetit][nMeme] = (dp[iBoat][iPetit][nMeme] + getDp(avant, valAvant, 1))%MOD;
		dp[iBoat][iPetit][nMeme] = (dp[iBoat][iPetit][nMeme] * nFacons(nMeme, taille[iPetit]))%MOD;
		//cout << "calc " << iBoat << " " << iPetit << " " << nMeme << " " << nFacons(nMeme, taille[iPetit]);
		//Si on reste sur le même intervalle
		for (int avant = 0; avant < iBoat; ++avant)
			dp[iBoat][iPetit][nMeme] = (dp[iBoat][iPetit][nMeme] + getDp(avant, iPetit, nMeme + 1))%MOD;
		//Si cetait le premier
		dp[iBoat][iPetit][nMeme] = (dp[iBoat][iPetit][nMeme] + getDp(-1, iPetit, nMeme));
	//	cout << "DP " << iBoat << " " << iPetit << " " << nMeme << " " << dp[iBoat][iPetit][nMeme] << endl;
	}
	return dp[iBoat][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][j][k] = INDEFINI;

	int sum = 0;
	for (int dernier = 0; dernier < nBoats; ++dernier)
		for (int iPetit = 0; iPetit < sz(vals) - 1; ++iPetit)
			sum = (sum + getDp(dernier, iPetit, 1))%MOD;
	/*
	for (int dernier = 0; dernier < nBoats; ++dernier)
		for (int iPetit = 0; iPetit < sz(vals) - 1; ++iPetit){
			cout << "DP " << dernier << " " << iPetit << " " << getDp(dernier, iPetit, 1) << endl;
		}
	*/cout << sum << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 40396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 313 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -