Submission #390655

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
390655	2021-04-16T13:09:20 Z	Blagojce	Boat (APIO16_boat)	C++11	100 / 100	1329 ms	2504 KB

boat

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 1e10;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 505;


ll modpow(ll x, ll n){
	if(n == 0) return 1%mod;
	ll u = modpow(x, n/2);
	u = (u * u) % mod;
	if(n % 2) u = (u * x) % mod;
	return u;
}
ll inverse(ll x){
	return modpow(x, mod-2);
}

ll fakt[mxn];
ll ifakt[mxn];

ll BC[mxn][mxn];

ll bc1(ll n, ll k){
	if(n < k) return 0;
	return (fakt[n]*((ifakt[k]*ifakt[n-k]) % mod)) % mod;
}

ll precomp[mxn];

void pre(ll n){
	ll tot = 1;
	precomp[0] = 1;
	fr(i, 0, mxn-1){
		tot *= (n-i);
		tot %= mod;
		precomp[i+1] = tot;
	}
}
ll bc2(ll n, ll k){
	if(n < k) return 0;
	
	return (precomp[k]*ifakt[k])%mod;
}

ll store[mxn];

void pre2(ll a_len){
	fr(LEN, 2, mxn){
		store[LEN] = 0;
		fr(len, 2, LEN+1){
			ll ways = (bc2(a_len, len)*BC[LEN-2][len-2])%mod;
			store[LEN] += ways;
			store[LEN] %= mod;
		}
	}
}



int n;
ll l[mxn], r[mxn];

ll DP1[mxn];
ll DP2[mxn];


void solve(){
	
	fakt[0] = 1;
	fr(i, 1, mxn){
		fakt[i] = (fakt[i-1]*i)%mod;
	}
	fr(i, 0, mxn){
		ifakt[i] = inverse(fakt[i]);
	}
	fr(i, 0, mxn){
		fr(j, 0, mxn){
			BC[i][j] = bc1(i, j);
		}
	}
	

	cin >> n;
	fr(i, 0, n){
		cin >> l[i] >> r[i];
	}
	
	vector<pair<ll, int> > v;
	fr(i, 0, n){
		v.pb({l[i], -i});
		v.pb({r[i],i+1});
	}
	
	sort(all(v));
	
	vector<int> active;
	
	DP1[0] = 1;
	
	ll prv = 0;
	
	ll a_len;
	
	for(auto u : v){
		
		int id = u.nd;
		
		if(id > 0){
			a_len = u.st - prv;
		}
		else{
			a_len = u.st - prv-1;
		}
				
		fr(i, 0, mxn) DP2[i] = DP1[i];
		
		pre(a_len);
		
		
		pre2(a_len);
		
		
		fr(i, 0, (int)active.size()){
			ll sum = 0;
			fr(k, 0, active[i]+1){
				sum += DP1[k];
				sum %= mod;
			}
			
			fr(j, i, (int)active.size()){
				
				if(i == j){
					ll ways = a_len % mod;

					DP2[active[j]+1] += (ways*sum)%mod;
					DP2[active[j]+1] %= mod;
				}
				else{
					DP2[active[j]+1] += (store[j-i+1] * sum) % mod;
				}	
			}
		}
		
		fr(i, 0, mxn){
			DP1[i] = DP2[i];
		}
		
		if(id <= 0){
			prv = u.st-1; 
			active.pb(-id);
			sort(all(active));
			
		}else{
			prv = u.st;
			active.erase(find(all(active), id-1));
			sort(all(active));
		}
		
		
	}
	ll ans = 0;
	fr(i, 1, n+1){
		ans += DP1[i];
		ans %= mod;
	}
	
	cout<<ans<<endl;
}

int main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	742 ms	2356 KB	Output is correct
2	Correct	726 ms	2380 KB	Output is correct
3	Correct	726 ms	2360 KB	Output is correct
4	Correct	731 ms	2252 KB	Output is correct
5	Correct	754 ms	2372 KB	Output is correct
6	Correct	725 ms	2360 KB	Output is correct
7	Correct	729 ms	2380 KB	Output is correct
8	Correct	735 ms	2360 KB	Output is correct
9	Correct	759 ms	2380 KB	Output is correct
10	Correct	729 ms	2252 KB	Output is correct
11	Correct	740 ms	2380 KB	Output is correct
12	Correct	737 ms	2380 KB	Output is correct
13	Correct	731 ms	2380 KB	Output is correct
14	Correct	748 ms	2376 KB	Output is correct
15	Correct	727 ms	2380 KB	Output is correct
16	Correct	642 ms	2380 KB	Output is correct
17	Correct	624 ms	2380 KB	Output is correct
18	Correct	627 ms	2372 KB	Output is correct
19	Correct	644 ms	2380 KB	Output is correct
20	Correct	622 ms	2380 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	742 ms	2356 KB	Output is correct
2	Correct	726 ms	2380 KB	Output is correct
3	Correct	726 ms	2360 KB	Output is correct
4	Correct	731 ms	2252 KB	Output is correct
5	Correct	754 ms	2372 KB	Output is correct
6	Correct	725 ms	2360 KB	Output is correct
7	Correct	729 ms	2380 KB	Output is correct
8	Correct	735 ms	2360 KB	Output is correct
9	Correct	759 ms	2380 KB	Output is correct
10	Correct	729 ms	2252 KB	Output is correct
11	Correct	740 ms	2380 KB	Output is correct
12	Correct	737 ms	2380 KB	Output is correct
13	Correct	731 ms	2380 KB	Output is correct
14	Correct	748 ms	2376 KB	Output is correct
15	Correct	727 ms	2380 KB	Output is correct
16	Correct	642 ms	2380 KB	Output is correct
17	Correct	624 ms	2380 KB	Output is correct
18	Correct	627 ms	2372 KB	Output is correct
19	Correct	644 ms	2380 KB	Output is correct
20	Correct	622 ms	2380 KB	Output is correct
21	Correct	888 ms	2380 KB	Output is correct
22	Correct	958 ms	2380 KB	Output is correct
23	Correct	874 ms	2380 KB	Output is correct
24	Correct	936 ms	2364 KB	Output is correct
25	Correct	924 ms	2380 KB	Output is correct
26	Correct	1044 ms	2380 KB	Output is correct
27	Correct	1066 ms	2384 KB	Output is correct
28	Correct	1079 ms	2380 KB	Output is correct
29	Correct	1080 ms	2364 KB	Output is correct
30	Correct	750 ms	2380 KB	Output is correct
31	Correct	738 ms	2380 KB	Output is correct
32	Correct	750 ms	2380 KB	Output is correct
33	Correct	752 ms	2372 KB	Output is correct
34	Correct	735 ms	2380 KB	Output is correct
35	Correct	769 ms	2372 KB	Output is correct
36	Correct	740 ms	2380 KB	Output is correct
37	Correct	770 ms	2380 KB	Output is correct
38	Correct	760 ms	2380 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	2308 KB	Output is correct
2	Correct	183 ms	2336 KB	Output is correct
3	Correct	179 ms	2372 KB	Output is correct
4	Correct	189 ms	2252 KB	Output is correct
5	Correct	374 ms	2332 KB	Output is correct
6	Correct	183 ms	2332 KB	Output is correct
7	Correct	185 ms	2252 KB	Output is correct
8	Correct	201 ms	2336 KB	Output is correct
9	Correct	196 ms	2336 KB	Output is correct
10	Correct	195 ms	2340 KB	Output is correct
11	Correct	177 ms	2252 KB	Output is correct
12	Correct	196 ms	2332 KB	Output is correct
13	Correct	198 ms	2336 KB	Output is correct
14	Correct	175 ms	2252 KB	Output is correct
15	Correct	177 ms	2336 KB	Output is correct
16	Correct	147 ms	2252 KB	Output is correct
17	Correct	146 ms	2252 KB	Output is correct
18	Correct	149 ms	2252 KB	Output is correct
19	Correct	145 ms	2252 KB	Output is correct
20	Correct	155 ms	2344 KB	Output is correct

Subtask #4
42.0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	742 ms	2356 KB	Output is correct
2	Correct	726 ms	2380 KB	Output is correct
3	Correct	726 ms	2360 KB	Output is correct
4	Correct	731 ms	2252 KB	Output is correct
5	Correct	754 ms	2372 KB	Output is correct
6	Correct	725 ms	2360 KB	Output is correct
7	Correct	729 ms	2380 KB	Output is correct
8	Correct	735 ms	2360 KB	Output is correct
9	Correct	759 ms	2380 KB	Output is correct
10	Correct	729 ms	2252 KB	Output is correct
11	Correct	740 ms	2380 KB	Output is correct
12	Correct	737 ms	2380 KB	Output is correct
13	Correct	731 ms	2380 KB	Output is correct
14	Correct	748 ms	2376 KB	Output is correct
15	Correct	727 ms	2380 KB	Output is correct
16	Correct	642 ms	2380 KB	Output is correct
17	Correct	624 ms	2380 KB	Output is correct
18	Correct	627 ms	2372 KB	Output is correct
19	Correct	644 ms	2380 KB	Output is correct
20	Correct	622 ms	2380 KB	Output is correct
21	Correct	888 ms	2380 KB	Output is correct
22	Correct	958 ms	2380 KB	Output is correct
23	Correct	874 ms	2380 KB	Output is correct
24	Correct	936 ms	2364 KB	Output is correct
25	Correct	924 ms	2380 KB	Output is correct
26	Correct	1044 ms	2380 KB	Output is correct
27	Correct	1066 ms	2384 KB	Output is correct
28	Correct	1079 ms	2380 KB	Output is correct
29	Correct	1080 ms	2364 KB	Output is correct
30	Correct	750 ms	2380 KB	Output is correct
31	Correct	738 ms	2380 KB	Output is correct
32	Correct	750 ms	2380 KB	Output is correct
33	Correct	752 ms	2372 KB	Output is correct
34	Correct	735 ms	2380 KB	Output is correct
35	Correct	769 ms	2372 KB	Output is correct
36	Correct	740 ms	2380 KB	Output is correct
37	Correct	770 ms	2380 KB	Output is correct
38	Correct	760 ms	2380 KB	Output is correct
39	Correct	179 ms	2308 KB	Output is correct
40	Correct	183 ms	2336 KB	Output is correct
41	Correct	179 ms	2372 KB	Output is correct
42	Correct	189 ms	2252 KB	Output is correct
43	Correct	374 ms	2332 KB	Output is correct
44	Correct	183 ms	2332 KB	Output is correct
45	Correct	185 ms	2252 KB	Output is correct
46	Correct	201 ms	2336 KB	Output is correct
47	Correct	196 ms	2336 KB	Output is correct
48	Correct	195 ms	2340 KB	Output is correct
49	Correct	177 ms	2252 KB	Output is correct
50	Correct	196 ms	2332 KB	Output is correct
51	Correct	198 ms	2336 KB	Output is correct
52	Correct	175 ms	2252 KB	Output is correct
53	Correct	177 ms	2336 KB	Output is correct
54	Correct	147 ms	2252 KB	Output is correct
55	Correct	146 ms	2252 KB	Output is correct
56	Correct	149 ms	2252 KB	Output is correct
57	Correct	145 ms	2252 KB	Output is correct
58	Correct	155 ms	2344 KB	Output is correct
59	Correct	1119 ms	2380 KB	Output is correct
60	Correct	1133 ms	2380 KB	Output is correct
61	Correct	1113 ms	2380 KB	Output is correct
62	Correct	1126 ms	2380 KB	Output is correct
63	Correct	1159 ms	2380 KB	Output is correct
64	Correct	1329 ms	2380 KB	Output is correct
65	Correct	1315 ms	2380 KB	Output is correct
66	Correct	1319 ms	2380 KB	Output is correct
67	Correct	1315 ms	2504 KB	Output is correct
68	Correct	1315 ms	2380 KB	Output is correct
69	Correct	1098 ms	2380 KB	Output is correct
70	Correct	1079 ms	2380 KB	Output is correct
71	Correct	1089 ms	2380 KB	Output is correct
72	Correct	1091 ms	2372 KB	Output is correct
73	Correct	1086 ms	2380 KB	Output is correct
74	Correct	888 ms	2380 KB	Output is correct
75	Correct	868 ms	2376 KB	Output is correct
76	Correct	887 ms	2384 KB	Output is correct
77	Correct	864 ms	2500 KB	Output is correct
78	Correct	883 ms	2380 KB	Output is correct

Submission #390655

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0