Submission #40846

#	Time	Username	Problem	Language	Result	Execution time	Memory
40846		IvanC	Boat (APIO16_boat)	C++14	9 / 100	2036 ms	524288 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 501;
const ll MOD = (ll)1e9 + 7;
ll A[MAXN],B[MAXN],N;
vector<ll> dp[MAXN],sum[MAXN];
ll get_sum(ll idx,ll i,ll j){
	i -= A[idx];
	j -= A[idx];
	i = max(i,0LL);
	if(i > j) return 0;
	if(i == 0) return sum[idx][j];
	else return sum[idx][j] - sum[idx][i-1];
}
int main(){
	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> A[i] >> B[i];
		for(ll j = A[i];j<=B[i];j++){
			dp[i].push_back(0);
			sum[i].push_back(0);
		}
	}
	for(ll j = A[N];j<=B[N];j++){
		dp[N][j - A[N]] = 1;
		sum[N][j - A[N]] = dp[N][j - A[N]];
		if(j - A[N] != 0) sum[N][j - A[N]] += sum[N][j - A[N] - 1]; 
	}
	for(ll i = N-1;i>=1;i--){
		for(ll j = A[i];j<=B[i];j++){
			dp[i][j - A[i]] = 1;
			for(ll k = i+1;k<=N;k++){
				dp[i][j - A[i]] = (dp[i][j - A[i]] + get_sum(k,j+1,B[k])) % MOD;
			}
		}
		for(ll j = A[i];j<=B[i];j++){
			sum[i][j - A[i]] = dp[i][j - A[i]];
			if(j - A[i] != 0) sum[i][j - A[i]] += sum[i][j - A[i] - 1];
			sum[i][j - A[i]] %= MOD;
		}
	}
	ll tot = 0;
	for(ll i = 1;i<=N;i++) tot = (tot + sum[i].back()) % MOD;
	if(tot < 0) tot += MOD;
	cout << tot << endl;
	return 0;
}

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