oj.uz

Submission #261978

# Submission time Handle Problem Language Result Execution time Memory
261978 2020-08-12T08:43:02 Z amoo_safar Boat (APIO16_boat) C++14
36 / 100
 2000 ms 8952 KB 
#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]) );
					dp[II][i][cnt] %= Mod;
				}
			}
			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 );
					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];
			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;
		}
	}
	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 1093 ms 8824 KB Output is correct
2 Correct 1139 ms 8832 KB Output is correct
3 Correct 1105 ms 8952 KB Output is correct
4 Correct 1098 ms 8824 KB Output is correct
5 Correct 1054 ms 8832 KB Output is correct
6 Correct 1053 ms 8824 KB Output is correct
7 Correct 1062 ms 8832 KB Output is correct
8 Correct 1067 ms 8952 KB Output is correct
9 Correct 1054 ms 8832 KB Output is correct
10 Correct 1147 ms 8952 KB Output is correct
11 Correct 1192 ms 8952 KB Output is correct
12 Correct 1112 ms 8952 KB Output is correct
13 Correct 1070 ms 8824 KB Output is correct
14 Correct 1096 ms 8828 KB Output is correct
15 Correct 1073 ms 8824 KB Output is correct
16 Correct 338 ms 8704 KB Output is correct
17 Correct 360 ms 8704 KB Output is correct
18 Correct 335 ms 8824 KB Output is correct
19 Correct 340 ms 8704 KB Output is correct
20 Correct 330 ms 8824 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 8824 KB Output is correct
2 Correct 1139 ms 8832 KB Output is correct
3 Correct 1105 ms 8952 KB Output is correct
4 Correct 1098 ms 8824 KB Output is correct
5 Correct 1054 ms 8832 KB Output is correct
6 Correct 1053 ms 8824 KB Output is correct
7 Correct 1062 ms 8832 KB Output is correct
8 Correct 1067 ms 8952 KB Output is correct
9 Correct 1054 ms 8832 KB Output is correct
10 Correct 1147 ms 8952 KB Output is correct
11 Correct 1192 ms 8952 KB Output is correct
12 Correct 1112 ms 8952 KB Output is correct
13 Correct 1070 ms 8824 KB Output is correct
14 Correct 1096 ms 8828 KB Output is correct
15 Correct 1073 ms 8824 KB Output is correct
16 Correct 338 ms 8704 KB Output is correct
17 Correct 360 ms 8704 KB Output is correct
18 Correct 335 ms 8824 KB Output is correct
19 Correct 340 ms 8704 KB Output is correct
20 Correct 330 ms 8824 KB Output is correct
21 Execution timed out 2031 ms 8820 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 8704 KB Output is correct
2 Correct 70 ms 8752 KB Output is correct
3 Correct 73 ms 8704 KB Output is correct
4 Correct 63 ms 8704 KB Output is correct
5 Correct 59 ms 8704 KB Output is correct
6 Correct 65 ms 8704 KB Output is correct
7 Correct 93 ms 8824 KB Output is correct
8 Correct 79 ms 8704 KB Output is correct
9 Correct 73 ms 8704 KB Output is correct
10 Correct 80 ms 8704 KB Output is correct
11 Correct 65 ms 8704 KB Output is correct
12 Correct 64 ms 8704 KB Output is correct
13 Correct 72 ms 8704 KB Output is correct
14 Correct 67 ms 8704 KB Output is correct
15 Correct 68 ms 8824 KB Output is correct
16 Correct 59 ms 8704 KB Output is correct
17 Correct 58 ms 8704 KB Output is correct
18 Correct 58 ms 8704 KB Output is correct
19 Correct 57 ms 8704 KB Output is correct
20 Correct 61 ms 8704 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1093 ms 8824 KB Output is correct
2 Correct 1139 ms 8832 KB Output is correct
3 Correct 1105 ms 8952 KB Output is correct
4 Correct 1098 ms 8824 KB Output is correct
5 Correct 1054 ms 8832 KB Output is correct
6 Correct 1053 ms 8824 KB Output is correct
7 Correct 1062 ms 8832 KB Output is correct
8 Correct 1067 ms 8952 KB Output is correct
9 Correct 1054 ms 8832 KB Output is correct
10 Correct 1147 ms 8952 KB Output is correct
11 Correct 1192 ms 8952 KB Output is correct
12 Correct 1112 ms 8952 KB Output is correct
13 Correct 1070 ms 8824 KB Output is correct
14 Correct 1096 ms 8828 KB Output is correct
15 Correct 1073 ms 8824 KB Output is correct
16 Correct 338 ms 8704 KB Output is correct
17 Correct 360 ms 8704 KB Output is correct
18 Correct 335 ms 8824 KB Output is correct
19 Correct 340 ms 8704 KB Output is correct
20 Correct 330 ms 8824 KB Output is correct
21 Execution timed out 2031 ms 8820 KB Time limit exceeded
22 Halted 0 ms 0 KB -