Submission #624919

#	Time	Username	Problem	Language	Result	Execution time	Memory
624919		QwertyPi	Boat (APIO16_boat)	C++14	100 / 100	1108 ms	8656 KiB

boat

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

const int N = 520;
const int M = 1e9 + 7;
int a[N], b[N];
int d[N * 2];
int dp[2][N * 2][N];

int n, m;

int pm(int a, int b){
	if(b == 0) return 1;
	return pm(a * a % M, b / 2) * (b % 2 ? a : 1) % M;
}

int mi(int a){
	return pm(a, M - 2);
}

int inv[N];
int32_t main(){
	cin >> n;
	for(int i = 0; i <= N; i++) inv[i] = mi(i);
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	vector<int> sp;
	sp.push_back(0);
	sp.push_back(1);
	for(int i = 0; i < n; i++){
		sp.push_back(a[i]);
		sp.push_back(b[i] + 1);
	}
	sort(sp.begin(), sp.end());
	sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
	m = sp.size();
	{
		map<int, int> M;
		for(int i = 0; i < m; i++) M[sp[i]] = i;
		for(int i = 0; i < n; i++) a[i] = M[a[i]], b[i] = M[b[i] + 1];
	}
	for(int i = 0; i < m - 1; i++){
		d[i] = sp[i + 1] - sp[i];
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[(i + 1) % 2][j][k] = dp[i % 2][j][k];
			}
		}
		int s[m + 1] = {0};
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				s[j + 1] += dp[i % 2][j][k];
			}
			s[j] %= M;
			s[j + 1] += s[j];
		}
		for(int j = a[i]; j < b[i]; j++){
			dp[(i + 1) % 2][j][1] += (s[j] + 1) * d[j] % M;
			for(int k = 1; k < n; k++){
				dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * (d[j] - k) % M * inv[k + 1] % M;
			}
		}
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[(i + 1) % 2][j][k] %= M;
			}
		}
	}
	
	for(int j = 0; j < m; j++){
		for(int k = 1; k <= n; k++){
			ans += dp[n % 2][j][k];
		}
	}
	ans %= M;
	cout << ans << endl;
}

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:27:37: warning: iteration 520 invokes undefined behavior [-Waggressive-loop-optimizations]
   27 |  for(int i = 0; i <= N; i++) inv[i] = mi(i);
      |                              ~~~~~~~^~~~~~~
boat.cpp:27:19: note: within this loop
   27 |  for(int i = 0; i <= N; i++) inv[i] = mi(i);
      |                 ~~^~~~

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