Submission #20868

#	Time	Username	Problem	Language	Result	Execution time	Memory
20868		kdh9949	Boat (APIO16_boat)	C++98	100 / 100	959 ms	7136 KiB

boat

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

int n;
set<int> ss;
int a[505], b[505], seg[1005], c, q, t;
int dp[505][1005], dps[505][1005];
int ufac[505], dfacin[505], newcomb[1005][505];
int mod = 1000000007;

long long pow(long long n, int k){
	if(k == 1) return n;
	long long t = pow(n, k / 2);
	t *= t; t %= mod;
	if(k % 2) return t * n % mod;
	return t;
}

int modinv(int x){
	return (int)pow(x, mod - 2);
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d", a + i, b + i);
		ss.insert(a[i]); ss.insert(b[i] + 1);
	}
	ss.insert(0); ss.insert(1);
	for(set<int>::iterator it = ss.begin(); it != ss.end(); it++) seg[++c] = *it;
	for(int i = 1; i <= n; i++){
		a[i] = (int)(lower_bound(seg + 1, seg + c + 1, a[i]) - seg);
		b[i] = (int)(lower_bound(seg + 1, seg + c + 1, b[i] + 1) - seg);
	}
	dfacin[0] = modinv(2); q = 2;
	for(int i = 1; i < n; i++){
		q = (int)((long long)q * (i + 2) % mod);
		dfacin[i] = modinv(q);
	}
	for(int i = 1; i < c; i++){
		ufac[0] = (int)((long long)(seg[i + 1] - seg[i]) * (seg[i + 1] - seg[i] - 1) % mod);
		newcomb[i][0] = (int)((long long)ufac[0] * dfacin[0] % mod);
		for(int j = 1; j < n; j++){
			ufac[j] = (int)((long long)ufac[j - 1] * (seg[i + 1] - seg[i] + j) % mod);
			newcomb[i][j] = (int)((long long)ufac[j] * dfacin[j] % mod);
		}
	}
	dp[0][0] = 1;
	for(int i = 0; i < c; i++) dps[0][i] = 1;
	for(int i = 1; i <= n; i++){
		dps[i][0] = dps[i - 1][0];
		for(int j = 1; j < a[i]; j++) dps[i][j] = ((dps[i - 1][j] + dps[i][j - 1]) % mod - dps[i - 1][j - 1] + mod) % mod;
		for(int j = a[i]; j < b[i]; j++){
			dp[i][j] = dps[i - 1][j - 1];
			dps[i][j] = ((dps[i - 1][j] + dps[i][j - 1]) % mod - dps[i - 1][j - 1] + mod) % mod;
			dps[i][j] += (int)((long long)(seg[j + 1] - seg[j]) * dp[i][j] % mod);
			dps[i][j] %= mod;
			q = 0;
			for(int k = i - 1; k > 0; k--){
				if(a[k] <= j && j < b[k]){
					t = (int)((long long)newcomb[j][q] * dp[k][j] % mod);
					dps[i][j] += t;
					dps[i][j] %= mod;
					q++;
				}
			}
		}
		for(int j = b[i]; j < c; j++) dps[i][j] = ((dps[i - 1][j] + dps[i][j - 1]) % mod - dps[i - 1][j - 1] + mod) % mod;
	}
	printf("%d", (dps[n][c - 1] - 1 + mod) % mod);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:26:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:28:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", a + i, b + i);
                              ^

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