Submission #425320

#	Time	Username	Problem	Language	Result	Execution time	Memory
425320		ksun48	Boat (APIO16_boat)	C++14	58 / 100	1423 ms	30388 KiB

boat

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL n;
LL a[1100];
LL b[1100];
LL included[1100][1100];
LL length[1100];
LL dp[2][1100][1100];
LL lenchoose[1100][1100];
LL invlist[1100];
LL powmod(LL z1, LL e){
	if(e == 0) return 1;
	LL c = powmod(z1,e/2);
	c = (c*c) % MOD;
	if(e % 2 == 0) return c;
	return (c*z1)%MOD;
}
LL inv(LL z1){
	return powmod(z1,MOD-2) % MOD;
}

int main(){
	set<LL> st;
	cin >> n;
	st.insert(0);
	st.insert(1);
	int t1 = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		st.insert(a[i]);
		st.insert(b[i]+1);
		t1 += b[i]-a[i];
	}
	st.insert(1000000005);
	st.insert(1000000006);
	int cur = 0;
	for(int i = 1; i < 1100; i++){
		invlist[i] = inv(i);
	}
	/*if(t1 <= 1000000){
		return 0;
	}*/
	while(st.size() >= 2){
		set<LL>::iterator c = st.begin();
		int l = *c;
		c++;
		int r = *c;
		st.erase(st.begin());
		included[0][cur] = 0;
		included[n+1][cur] = 0;
		length[cur] = r-l;
		for(int i = 1; i <= n; i++){
			if(a[i] <= l && r-1 <= b[i]){
				included[i][cur] = 1;
			} else {
				included[i][cur] = 0;
			}
		}
		cur++;
	}
	included[0][0] = 1;	
	included[n+1][cur-1] = 1;
	dp[0][0][1] = 1;
	for(int i = 0; i < cur; i++){
		int l = length[i];
		for(int j = 0; j < 510; j++){
			if(j > l){
				lenchoose[i][j] = 0;
			} else if(j == 0){
				lenchoose[i][j] = 1;
			} else {
				lenchoose[i][j] = lenchoose[i][j-1];
				lenchoose[i][j] *= (LL)(l-j+1);
				lenchoose[i][j] %= MOD;
				lenchoose[i][j] *= invlist[j];
				lenchoose[i][j] %= MOD;
			}
		}
	}
	for(int s = 0; s <= n; s++){
		for(int j = 0; j < 1100; j++){
			for(int k = 0; k < 510; k++){
				dp[1-s%2][j][k] = 0;
			}
		}
		LL r = 0;
		for(int l = 1; l < cur; l++){
			for(int k = 1; k <= cur && k <= 510; k++) if(dp[s%2][l-1][k] != 0){
				r += lenchoose[l-1][k]*dp[s%2][l-1][k];
				r %= MOD;
			}
			dp[1-s%2][l][1] = r;
		}
		for(int l = 0; l < cur; l++){
			if(!included[s+1][l]){
				dp[1-s%2][l][1] = 0;
			}
		}
		int aa = s % 2;
		int bb = 1 - s % 2;
		for(int j = 0; j < cur; j++){
			for(int k = 1; k <= s+2; k++) if(dp[aa][j][k]) {
				dp[bb][j][k] += dp[aa][j][k];
				if(dp[bb][j][k] >= MOD) dp[bb][j][k] -= MOD;
				if(included[s+1][j]){
					dp[bb][j][k+1] += dp[aa][j][k];
					if(dp[bb][j][k+1] >= MOD) dp[bb][j][k+1] -= MOD;
				}
			}
		}
	}
	cout << (dp[1-n%2][cur-1][1]+MOD-1) % MOD << endl;
	return 0;
}

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