Submission #261987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261987	2020-08-12T08:52:55 Z	amoo_safar	Boat (APIO16_boat)	C++17	36 / 100	2000 ms	8952 KB

boat

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define int ll
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> edge;

const int Maxn = 1e3 + 10;
ll Inf = 1e9;
const int Log = 20;
const ll Mod = 1e9 + 7;

ll mul(ll a, ll b){
	a %= Mod;
	b %= Mod;
	return (a * b) % Mod;
}

ll pw(ll b, ll p){
	if(p == 0) return 1ll;
	if(p & 1ll) return mul(b, pw(b, p - 1ll));
	return pw(mul(b, b), p >> 1);
}
ll inv[Maxn * 4];

ll a[Maxn], b[Maxn];
set<ll> st;
vector<pll> V;

ll dp[2][1040][510];
ll sm[2][1040];



int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for(int i = 0; i < 4 * Maxn; i++) inv[i] = pw(i, Mod - 2);
	ll n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		b[i] ++;
		st.insert(a[i]);
		st.insert(b[i]);
		//assert(a[i] == b[i] - 1);
	}
	
	ll l = -1;
	for(auto x : st){
		if(l != -1) V.pb({l, x});
		l = x;
	}
	sort(all(V));
	ll S = 0;
	ll m = V.size();
	for(int I = 1; I <= n; I++){
		int II = I & 1;
		memset(dp[II], 0, sizeof dp[II]);
		memset(sm[II], 0, sizeof sm[II]);
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int cnt = 2; cnt <= I; cnt ++){
					//if(cnt > V[i].S - V[i].F) continue;
					dp[II][i][cnt] = mul( dp[II ^ 1][i][cnt - 1], mul((V[i].S - V[i].F) - cnt + 1, inv[cnt]) );
				}
			}
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				for(int j = 0; j < i; j++){
					dp[II][i][1] += mul( sm[II ^ 1][j], V[i].S - V[i].F );
					if(dp[II][i][1] >= Mod)
						dp[II][i][1] %= Mod;
				}
			}
		}
		
		for(int i = 0; i < m; i++){
			if( (a[I] <= V[i].F) && (V[i].S <= b[I]) ){
				dp[II][i][1] += (V[i].S - V[i].F);
				//S += (V[i].S - V[i].F);
				dp[II][i][1] %= Mod;
			}
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			dp[II][i][cnt] += dp[II ^ 1][i][cnt];
			if(dp[II][i][cnt] >= Mod)
				dp[II][i][cnt] -= Mod;
			
		}
		
		for(int i = 0; i < m; i++) for(int cnt = 1; cnt <= I; cnt ++){
			sm[II][i] += dp[II][i][cnt];
			//cerr << I << " " << dp[II][i][cnt] << "\n";
			//sm[II][i] %= Mod;
			if(sm[II][i] >= Mod)
				sm[II][i] -= Mod;
		}
	}
	ll ans = 0;
	for(int i = 0; i < m; i++) ans += sm[n & 1][i];
	cout << ((ans % Mod) + Mod) % Mod;
	return 0;
}

Compilation message

boat.cpp: In function 'int32_t main()':
boat.cpp:5:11: warning: unused variable 'second' [-Wunused-variable]
 #define S second
           ^
boat.cpp:61:5: note: in expansion of macro 'S'
  ll S = 0;
     ^

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	776 ms	8824 KB	Output is correct
2	Correct	678 ms	8832 KB	Output is correct
3	Correct	674 ms	8952 KB	Output is correct
4	Correct	724 ms	8952 KB	Output is correct
5	Correct	682 ms	8832 KB	Output is correct
6	Correct	648 ms	8832 KB	Output is correct
7	Correct	687 ms	8824 KB	Output is correct
8	Correct	741 ms	8832 KB	Output is correct
9	Correct	701 ms	8832 KB	Output is correct
10	Correct	717 ms	8824 KB	Output is correct
11	Correct	747 ms	8952 KB	Output is correct
12	Correct	670 ms	8832 KB	Output is correct
13	Correct	651 ms	8824 KB	Output is correct
14	Correct	668 ms	8832 KB	Output is correct
15	Correct	686 ms	8832 KB	Output is correct
16	Correct	279 ms	8764 KB	Output is correct
17	Correct	282 ms	8764 KB	Output is correct
18	Correct	285 ms	8764 KB	Output is correct
19	Correct	275 ms	8704 KB	Output is correct
20	Correct	288 ms	8824 KB	Output is correct

Subtask #2
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	776 ms	8824 KB	Output is correct
2	Correct	678 ms	8832 KB	Output is correct
3	Correct	674 ms	8952 KB	Output is correct
4	Correct	724 ms	8952 KB	Output is correct
5	Correct	682 ms	8832 KB	Output is correct
6	Correct	648 ms	8832 KB	Output is correct
7	Correct	687 ms	8824 KB	Output is correct
8	Correct	741 ms	8832 KB	Output is correct
9	Correct	701 ms	8832 KB	Output is correct
10	Correct	717 ms	8824 KB	Output is correct
11	Correct	747 ms	8952 KB	Output is correct
12	Correct	670 ms	8832 KB	Output is correct
13	Correct	651 ms	8824 KB	Output is correct
14	Correct	668 ms	8832 KB	Output is correct
15	Correct	686 ms	8832 KB	Output is correct
16	Correct	279 ms	8764 KB	Output is correct
17	Correct	282 ms	8764 KB	Output is correct
18	Correct	285 ms	8764 KB	Output is correct
19	Correct	275 ms	8704 KB	Output is correct
20	Correct	288 ms	8824 KB	Output is correct
21	Correct	1705 ms	8824 KB	Output is correct
22	Correct	1646 ms	8824 KB	Output is correct
23	Correct	1502 ms	8828 KB	Output is correct
24	Correct	1538 ms	8820 KB	Output is correct
25	Correct	1587 ms	8820 KB	Output is correct
26	Execution timed out	2045 ms	8820 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	8752 KB	Output is correct
2	Correct	69 ms	8764 KB	Output is correct
3	Correct	68 ms	8760 KB	Output is correct
4	Correct	64 ms	8752 KB	Output is correct
5	Correct	75 ms	8704 KB	Output is correct
6	Correct	80 ms	8824 KB	Output is correct
7	Correct	78 ms	8704 KB	Output is correct
8	Correct	85 ms	8704 KB	Output is correct
9	Correct	74 ms	8704 KB	Output is correct
10	Correct	77 ms	8824 KB	Output is correct
11	Correct	70 ms	8704 KB	Output is correct
12	Correct	61 ms	8824 KB	Output is correct
13	Correct	57 ms	8704 KB	Output is correct
14	Correct	58 ms	8760 KB	Output is correct
15	Correct	62 ms	8952 KB	Output is correct
16	Correct	49 ms	8704 KB	Output is correct
17	Correct	50 ms	8704 KB	Output is correct
18	Correct	59 ms	8744 KB	Output is correct
19	Correct	60 ms	8752 KB	Output is correct
20	Correct	57 ms	8704 KB	Output is correct

Subtask #4
0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	776 ms	8824 KB	Output is correct
2	Correct	678 ms	8832 KB	Output is correct
3	Correct	674 ms	8952 KB	Output is correct
4	Correct	724 ms	8952 KB	Output is correct
5	Correct	682 ms	8832 KB	Output is correct
6	Correct	648 ms	8832 KB	Output is correct
7	Correct	687 ms	8824 KB	Output is correct
8	Correct	741 ms	8832 KB	Output is correct
9	Correct	701 ms	8832 KB	Output is correct
10	Correct	717 ms	8824 KB	Output is correct
11	Correct	747 ms	8952 KB	Output is correct
12	Correct	670 ms	8832 KB	Output is correct
13	Correct	651 ms	8824 KB	Output is correct
14	Correct	668 ms	8832 KB	Output is correct
15	Correct	686 ms	8832 KB	Output is correct
16	Correct	279 ms	8764 KB	Output is correct
17	Correct	282 ms	8764 KB	Output is correct
18	Correct	285 ms	8764 KB	Output is correct
19	Correct	275 ms	8704 KB	Output is correct
20	Correct	288 ms	8824 KB	Output is correct
21	Correct	1705 ms	8824 KB	Output is correct
22	Correct	1646 ms	8824 KB	Output is correct
23	Correct	1502 ms	8828 KB	Output is correct
24	Correct	1538 ms	8820 KB	Output is correct
25	Correct	1587 ms	8820 KB	Output is correct
26	Execution timed out	2045 ms	8820 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Submission #261987

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0