Submission #41835

#	Time	Username	Problem	Language	Result	Execution time	Memory
41835		IvanC	Boat (APIO16_boat)	C++14	58 / 100	2020 ms	6508 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 501;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXN],dp2[MAXN][2*MAXN],somatorio1[MAXN];
ll precalc[MAXN],A[MAXN],B[MAXN],N,M;
vector<ll> intervalos;
ll binary_expo(ll val,ll pot){
	if(pot == 0) return 1LL;
	if(pot % 2 == 0){
		ll davez = binary_expo(val,pot/2);
		return (davez*davez) % MOD;
	} 
	return (val*binary_expo(val,pot-1)) % MOD;
}
int main(){
	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> A[i] >> B[i];
		B[i]++;
		intervalos.push_back(A[i]);
		intervalos.push_back(B[i]); 
	}
	sort(intervalos.begin(),intervalos.end());
	intervalos.erase(unique(intervalos.begin(),intervalos.end()),intervalos.end());
	M = intervalos.size() - 2;
	ll tot = 0;
	for(int v = M;v>=0;v--){
		memset(dp,0,sizeof(dp));
		ll tam = intervalos[v+1] - intervalos[v];
		ll vaiate = min(tam,N);
		for(ll i = 2;i<=vaiate;i++){
			precalc[i] = (tam - i + 1)*binary_expo(i,MOD-2);
			precalc[i] %= MOD;
		}
		for(ll i = N;i>=1;i--){
			if(!(A[i] <= intervalos[v] && intervalos[v+1] <= B[i] )) continue;
			dp[i][1] = 1;
			for(ll j = i+1;j<=N;j++){
				dp[i][1] += somatorio1[j];
			}
			dp[i][1] %= MOD;
			dp[i][1] = (dp[i][1] * tam) % MOD;
			for(ll j = i + 1;j<=N;j++){
				for(ll k = 2;k<=vaiate;k++){
					dp[i][k] += dp[j][k-1];
				}
			}
			dp2[i][v] = dp[i][1];
			for(ll k = 2;k<=vaiate;k++){
				dp[i][k] %= MOD;
				dp[i][k] *= precalc[k];
				dp[i][k] %= MOD;
				dp2[i][v] += dp[i][k];
			}
			dp2[i][v] %= MOD;
			tot += dp2[i][v];
			tot %= MOD;
		}
		for(int i = 1;i<=N;i++){
			somatorio1[i] += dp2[i][v];
			somatorio1[i] %= MOD;
		}
	}
	cout << tot << endl;
	return 0;
}

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