oj.uz

Submission #61201

# Submission time Handle Problem Language Result Execution time Memory
61201 2018-07-25T11:05:47 Z istlemin Boat (APIO16_boat) C++14
0 / 100
 2000 ms 525312 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll mod = 1e9+7;

vi posLast;
vi posLastStart;
vi a;
vi b;
ll n;

ll getNum(ll lastI,ll index){
	if(index==n) return 1;
	ll last = posLast[lastI];
	ll ans = getNum(lastI,index+1)%mod;
	rep(i,max(last+1,a[index]),b[index]+1){
        ans = (ans + getNum(posLastStart[index]+i-a[index],index+1))%mod;
	}
    return ans%mod;
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n;
    a.resize(n);
    b.resize(n);
    posLastStart.resize(n);
    posLast.push_back(-1);
    rep(i,0,n) {
		cin>>a[i]>>b[i];
		posLastStart[i] = posLast.size();
		rep(j,a[i],b[i]+1) posLast.push_back(j);
	}

    cout<<(getNum(0,0)+mod-1)%mod<<endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 525312 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -