| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 433630 |
2021-06-20T08:49:09 Z |
Mounir |
Boat (APIO16_boat) |
C++14 |
|
396 ms |
32972 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()
#define int long long
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 << " " << binome[situation] << endl;
return binome[situation];
}
int getDp(int iBoat, int iPetit, int nMeme){
if (iBoat == -1){
//cout << "get " << iPetit << " " << taille[iPetit] << " " << nMeme << " " << nFacons(nMeme, taille[iPetit]) << endl;
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];
}
for (int ind = 0; ind < sz(vals) - 1; ++ind){
int bign = taille[ind], res = bign;
for (int k = 2; k <= nBoats; ++k){
binome[{k - 1, bign}] = res;
res = (res * bign - k + 1)%MOD;
res = (res * expo(k, MOD - 2))%MOD;
}
binome[{nBoats, bign}] = res;
}
//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)
dp[i%2][j][k] = INDEFINI;
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);
//cout << "DP " << i << " " << j << " " << k << " " << getDp(i, j , k) << endl;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
32972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
32972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
396 ms |
2220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
186 ms |
32972 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
