제출 #61203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61203		istlemin	Boat (APIO16_boat)	C++14	9 / 100	2056 ms	525312 KiB

boat

#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;

vector<vi> mem;

ll getNum(ll lastI,ll index){
	if(index==n) return 1;
	if(mem[lastI][index]!=-1) return mem[lastI][index];
	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  mem[lastI][index] = (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);
	}

	mem.resize(posLastStart.size()+1,vi(n+1,-1));
    cout<<(getNum(0,0)+mod-1)%mod<<endl;
}

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