oj.uz

답안 #261982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261982 2020-08-12T08:46:50 Z amoo_safar Boat (APIO16_boat) C++14
36 / 100
 2000 ms 9080 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]) );
					if(dp[II][i][cnt] >= Mod)
						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 );
					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];
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 1186 ms 8832 KB Output is correct
2 Correct 1105 ms 8872 KB Output is correct
3 Correct 1146 ms 8832 KB Output is correct
4 Correct 1199 ms 8832 KB Output is correct
5 Correct 1115 ms 8832 KB Output is correct
6 Correct 1097 ms 8824 KB Output is correct
7 Correct 1218 ms 8832 KB Output is correct
8 Correct 1163 ms 8832 KB Output is correct
9 Correct 1161 ms 8832 KB Output is correct
10 Correct 1095 ms 8832 KB Output is correct
11 Correct 1138 ms 8952 KB Output is correct
12 Correct 1065 ms 8832 KB Output is correct
13 Correct 1062 ms 8832 KB Output is correct
14 Correct 1071 ms 9080 KB Output is correct
15 Correct 1060 ms 8824 KB Output is correct
16 Correct 329 ms 8824 KB Output is correct
17 Correct 342 ms 8824 KB Output is correct
18 Correct 343 ms 8704 KB Output is correct
19 Correct 355 ms 8764 KB Output is correct
20 Correct 340 ms 8704 KB Output is correct

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1186 ms 8832 KB Output is correct
2 Correct 1105 ms 8872 KB Output is correct
3 Correct 1146 ms 8832 KB Output is correct
4 Correct 1199 ms 8832 KB Output is correct
5 Correct 1115 ms 8832 KB Output is correct
6 Correct 1097 ms 8824 KB Output is correct
7 Correct 1218 ms 8832 KB Output is correct
8 Correct 1163 ms 8832 KB Output is correct
9 Correct 1161 ms 8832 KB Output is correct
10 Correct 1095 ms 8832 KB Output is correct
11 Correct 1138 ms 8952 KB Output is correct
12 Correct 1065 ms 8832 KB Output is correct
13 Correct 1062 ms 8832 KB Output is correct
14 Correct 1071 ms 9080 KB Output is correct
15 Correct 1060 ms 8824 KB Output is correct
16 Correct 329 ms 8824 KB Output is correct
17 Correct 342 ms 8824 KB Output is correct
18 Correct 343 ms 8704 KB Output is correct
19 Correct 355 ms 8764 KB Output is correct
20 Correct 340 ms 8704 KB Output is correct
21 Execution timed out 2088 ms 8832 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 8704 KB Output is correct
2 Correct 70 ms 8704 KB Output is correct
3 Correct 67 ms 8704 KB Output is correct
4 Correct 65 ms 8704 KB Output is correct
5 Correct 63 ms 8828 KB Output is correct
6 Correct 69 ms 8704 KB Output is correct
7 Correct 68 ms 8704 KB Output is correct
8 Correct 65 ms 8704 KB Output is correct
9 Correct 66 ms 8704 KB Output is correct
10 Correct 73 ms 8824 KB Output is correct
11 Correct 65 ms 8704 KB Output is correct
12 Correct 68 ms 8824 KB Output is correct
13 Correct 66 ms 8704 KB Output is correct
14 Correct 61 ms 8704 KB Output is correct
15 Correct 63 ms 8704 KB Output is correct
16 Correct 55 ms 8704 KB Output is correct
17 Correct 52 ms 8704 KB Output is correct
18 Correct 50 ms 8704 KB Output is correct
19 Correct 51 ms 8704 KB Output is correct
20 Correct 53 ms 8704 KB Output is correct

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1186 ms 8832 KB Output is correct
2 Correct 1105 ms 8872 KB Output is correct
3 Correct 1146 ms 8832 KB Output is correct
4 Correct 1199 ms 8832 KB Output is correct
5 Correct 1115 ms 8832 KB Output is correct
6 Correct 1097 ms 8824 KB Output is correct
7 Correct 1218 ms 8832 KB Output is correct
8 Correct 1163 ms 8832 KB Output is correct
9 Correct 1161 ms 8832 KB Output is correct
10 Correct 1095 ms 8832 KB Output is correct
11 Correct 1138 ms 8952 KB Output is correct
12 Correct 1065 ms 8832 KB Output is correct
13 Correct 1062 ms 8832 KB Output is correct
14 Correct 1071 ms 9080 KB Output is correct
15 Correct 1060 ms 8824 KB Output is correct
16 Correct 329 ms 8824 KB Output is correct
17 Correct 342 ms 8824 KB Output is correct
18 Correct 343 ms 8704 KB Output is correct
19 Correct 355 ms 8764 KB Output is correct
20 Correct 340 ms 8704 KB Output is correct
21 Execution timed out 2088 ms 8832 KB Time limit exceeded
22 Halted 0 ms 0 KB -