Submission #1109970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109970		dsyz	Boat (APIO16_boat)	C++17	0 / 100	432 ms	524288 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll mod = 1e9 + 7;
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	ll A[N], B[N];
	for(ll i = 0;i < N;i++){
		cin>>A[i]>>B[i];
	}
	vector<ll> dp[N];
	for(ll w = A[0];w <= B[0];w++){
		dp[0].push_back(1);
	}
	for(ll i = 1;i < N;i++){
		ll ptr = -1;
		ll prevsum = 0;
		for(ll j = A[i];j <= B[i];j++){
			while(ptr + 1 < ll(dp[i - 1].size()) && A[i - 1] + (ptr + 1) < j){
				ptr++;
				prevsum += dp[i - 1][ptr];
				prevsum %= mod;
			}
			dp[i].push_back((prevsum + 1) % mod);
		}
	}
	ll sum = 0;
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < ll(dp[i].size());j++){
			sum += dp[i][j];
			sum %= mod;
		}
	}
	cout<<sum<<'\n';
}

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