oj.uz

Submission #261984

# Submission time Handle Problem Language Result Execution time Memory
261984 2020-08-12T08:50:10 Z amoo_safar Boat (APIO16_boat) C++17
0 / 100
 848 ms 8832 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( (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 );
				}
			}
		}
		
		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];
			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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 848 ms 8832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 848 ms 8832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 8704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 848 ms 8832 KB Output isn't correct
2 Halted 0 ms 0 KB -