oj.uz

Submission #1109970

# Submission time Handle Problem Language Result Execution time Memory
1109970 2024-11-08T09:24:14 Z dsyz Boat (APIO16_boat) C++17
0 / 100
 432 ms 524288 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 432 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -