oj.uz

Submission #540969

# Submission time Handle Problem Language Result Execution time Memory
540969 2022-03-22T05:31:02 Z amunduzbaev Boat (APIO16_boat) C++17
0 / 100
 1481 ms 524288 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int mod = 1e9 + 7;

int bp(int a, int b){
	int r=1;
	while(b){
		if(b&1) r = r * 1ll * a % mod;
		a = a * 1ll * a % mod; b >>= 1;
	} return r;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	freopen("in.txt", "r", stdin);
	
	int n; cin>>n;
	vector<int> a(2 * n), p(2 * n), og;
	iota(p.begin(), p.end(), 0);
	for(int i=0;i<n;i++){
		cin>>a[i<<1]>>a[i<<1|1];
		a[i<<1|1]++;
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (a[i] < a[j]);
	});
	int last=0;
	for(int i=0, j=0;i<2*n;last++){
		og.push_back(a[p[i]]);
		while(j<2*n && a[p[j]] == a[p[i]]) j++;
		while(i < j) a[p[i]] = last, i++;
	}
	
	vector<int> f(n + 1), inv(n + 1);
	f[0] = inv[0] = 1;
	for(int i=1;i<=n;i++){
		f[i] = f[i-1] * 1ll * i % mod;
		inv[i] = bp(f[i], mod - 2);
	}
	
	//~ for(int i=0;i<10;i++) cout<<a[i<<1]<<" "<<a[i<<1|1]<<"\n";
	
	auto C = [&](int n, int k){
		if(n < k) return 0ll;
		return f[n] * 1ll * inv[k] % mod * inv[n - k] % mod;
	};

	vector<vector<int>> cnt(n + 1, vector<int>(last));
	for(int c=1;c<=n;c++){
		for(int k=0;k+1<last;k++){
			int x = og[k+1] - og[k], f = x;
			for(int j=0;j<c && j<x;j++){
				cnt[c][k] = (cnt[c][k] + C(c - 1, j) * f % mod * inv[j + 1]) % mod;
				f = f * 1ll * (x - j - 1) % mod; 
			}
		}
	}
	
	int res = 0;
	vector<vector<int>> dp(n, vector<int>(last));
	for(int i=0;i<n;i++){
		int l = a[i<<1], r = a[i<<1|1];
		for(int k=l;k<r;k++){
			int c=1;
			for(int j=i-1;~j;j--){
				if(k){
					dp[i][k] = (dp[i][k] + dp[j][k-1] * 1ll * cnt[c][k]) % mod;
				}
				if(a[j<<1] <= k && k < a[j<<1|1]) c++;
			}
			
			dp[i][k] = (dp[i][k] + cnt[c][k]) % mod;
			//~ cout<<dp[i][k]<<endl;
			//~ if(k) dp[i][k] = (dp[i][k] + dp[i][k-1]) % mod;
		}
		
		for(int k=1;k<last;k++) dp[i][k] = (dp[i][k] + dp[i][k-1]) % mod;
		res = (res + dp[i][last - 1]) % mod;
	}
	
	cout<<res<<"\n";
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:19:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1481 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1481 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1406 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 1481 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -