Submission #261977

#	Time	Username	Problem	Language	Result	Execution time	Memory
261977		amoo_safar	Boat (APIO16_boat)	C++14	58 / 100	2032 ms	14584 KiB

boat

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimise ("ofast")
#pragma GCC optimise("unroll-loops")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000000;
const ll LOG = 25;

int  dp[2][N * 4][N], ps[N][N * 4], a[N], b[N], inv[N], n, in;
vector<int> T;

inline ll POW(ll x, ll t){
	ll res = 1;
	while(t){
		if (t & 1) res = res * x % MOD;
		t >>= 1;
		x = x * x % MOD;
	}
	return res;
}

inline void calc(){
	for (int i = 0; i < N; i++) inv[i] = POW(i, MOD - 2);
}
vector<pii> TT;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	calc();
	for (int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		b[i] ++; 
		T.pb(a[i]);
		T.pb(b[i]);
	}
	sort(all(T));
	T.resize(unique(all(T)) - T.begin());
	for (int i = 0; i < T.size() - 1; i++){
		if (T[i + 1] - 1 >= T[i]){
			TT.pb({T[i], T[i + 1]});
		}
	}
	bool f = 1;
	in = TT.size();
	for (int i = 0; i < N * 4; i++) ps[0][i] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= in; j++) for (int k = 1; k <= min(i, TT[j - 1].S - TT[j - 1].F); k++) dp[f][j][k] = 0;
		for (int j = 1; j <= in; j++){
			for (int k = 1; k <= min(i, TT[j - 1].S - TT[j - 1].F); k++){
				dp[f][j][k] = dp[f ^ 1][j][k];
				if (TT[j - 1].F >= b[i] || TT[j - 1].S <= a[i]) continue;
				if (k == 1) dp[f][j][k] += ps[i - 1][j - 1], dp[f][j][k] %= MOD;
				else{
					dp[f][j][k] += dp[f ^ 1][j][k - 1];
					dp[f][j][k] %= MOD;
				}
			}
		}
		ps[i][0] = 1;
		for (int j = 1; j <= in; j++){
			ps[i][j] = ps[i][j - 1];
			ll res = 1;
			ll ted = TT[j - 1].S - TT[j - 1].F;
			for (int k = 1; k <= min(i, TT[j - 1].S - TT[j - 1].F); k++){
				res = res * (ted - k + 1) % MOD;
				res = res * inv[k] % MOD;
				ps[i][j] += dp[f][j][k] * 1ll * res % MOD;
				ps[i][j] %= MOD;
			}
		}
		f ^= 1;
	}
	cout << (((ps[n][in] - 1) % MOD) + MOD) % MOD;


	return 0;
}

Compilation message (stderr)

boat.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
boat.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
 
boat.cpp: In function 'int32_t main()':
boat.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < T.size() - 1; i++){
                  ~~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42