Submission #40847

#	Time	Username	Problem	Language	Result	Execution time	Memory
40847		IvanC	Boat (APIO16_boat)	C++14	31 / 100	1523 ms	16412 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];
inline ll get_sum(int idx,int i,int j){
	i -= A[idx];
	j -= A[idx];
	i = max(i,0);
	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];
		dp[i].assign(B[i] - A[i] + 1,0);
		sum[i].assign(B[i] - A[i] + 1,0);
	}
	for(int 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(int i = N-1;i>=1;i--){
		for(int 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]));
			}
			dp[i][j - A[i]] %= MOD;
		}
		for(int 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(int 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: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42