oj.uz

Submission #667329

# Submission time Handle Problem Language Result Execution time Memory
667329 2022-12-01T06:42:10 Z NothingXD Boat (APIO16_boat) C++17
9 / 100
 757 ms 7524 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
    ull q = (ull)((L(m) * a) >> 64);
    ull r = a - q * b; // can be proven that 0 <= r < 2*b
    return r >= b ? r - b : r;
  }
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 500 + 10;
const int mod = 1e9 + 7;
int n, dp[maxn][maxn << 1], C[maxn][maxn], CC[maxn << 1][maxn], f[maxn << 1][maxn], inv[maxn], a[maxn], b[maxn];
vector<int> num;

int add(int x, int y){
	int res = x + y;
	if (res >= mod) return res - mod;
	if (res < 0) return res + mod;
	return res;
}

int pwr(int a, int b){
	int res = 1;
	for (; b; b>>=1, a = 1ll * a * a % mod) if (b & 1) res = 1ll * res * a % mod;
	return res;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		num.push_back(a[i]);
		num.push_back(b[i]+1);
	}

	num.push_back(0);

	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));

	for (int i = 1; i <= n; i++){
		inv[i] = pwr(i, mod-2);
	}

	for (int i = 0; i <= n; i++) C[i][0] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			C[i][j] = add(C[i-1][j-1], C[i-1][j]);
		}
	}


	for (int i = 0; i + 1 < num.size(); i++){
		int tmp = num[i+1] - num[i];
		CC[i][0] = 1;
		for (int j = 1; j <= n; j++){
			CC[i][j] = 1ll * CC[i][j-1] * (tmp - j + 1) * inv[j] % mod;
		}
	}
	for (int i = 0; i + 1 < num.size(); i++){
		int tmp = num[i+1] - num[i];
		for (int j = 1; j <= n; j++){
			for (int k = 1; k <= j; k++){
				f[i][j] = add(f[i][j], 1ll * CC[i][k] * C[j-1][k-1] % mod);
			}
		}
	}


	for (int i = 0; i + 1 < num.size(); i++) dp[0][i] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j + 1 < num.size(); j++){
			dp[i][j] = dp[i][j-1];
			if (a[i] > num[j] || b[i] < num[j]) continue;
			int cnt = 1;
			for (int k = i-1; ~k; k--){
				dp[i][j] = add(dp[i][j], 1ll * dp[k][j-1] * f[j][cnt] % mod);
				if (a[k] <= num[j] && num[j] <= b[k]) cnt++;
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= n; i++){
		ans = add(ans, dp[i][num.size()-2]);
	}
	cout << ans << '\n';
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:83:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (int i = 0; i + 1 < num.size(); i++){
      |                  ~~~~~~^~~~~~~~~~~~
boat.cpp:90:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i + 1 < num.size(); i++){
      |                  ~~~~~~^~~~~~~~~~~~
boat.cpp:91:7: warning: unused variable 'tmp' [-Wunused-variable]
   91 |   int tmp = num[i+1] - num[i];
      |       ^~~
boat.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for (int i = 0; i + 1 < num.size(); i++) dp[0][i] = 1;
      |                  ~~~~~~^~~~~~~~~~~~
boat.cpp:102:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for (int j = 1; j + 1 < num.size(); j++){
      |                   ~~~~~~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 7244 KB Output is correct
2 Correct 533 ms 7320 KB Output is correct
3 Correct 524 ms 7260 KB Output is correct
4 Correct 515 ms 7360 KB Output is correct
5 Correct 530 ms 7420 KB Output is correct
6 Correct 511 ms 7524 KB Output is correct
7 Correct 534 ms 7216 KB Output is correct
8 Correct 534 ms 7360 KB Output is correct
9 Correct 531 ms 7336 KB Output is correct
10 Correct 534 ms 7288 KB Output is correct
11 Correct 529 ms 7244 KB Output is correct
12 Correct 522 ms 7280 KB Output is correct
13 Correct 517 ms 7328 KB Output is correct
14 Correct 516 ms 7232 KB Output is correct
15 Correct 530 ms 7360 KB Output is correct
16 Correct 94 ms 4036 KB Output is correct
17 Correct 102 ms 4004 KB Output is correct
18 Correct 115 ms 4052 KB Output is correct
19 Correct 108 ms 3984 KB Output is correct
20 Correct 98 ms 4068 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 7244 KB Output is correct
2 Correct 533 ms 7320 KB Output is correct
3 Correct 524 ms 7260 KB Output is correct
4 Correct 515 ms 7360 KB Output is correct
5 Correct 530 ms 7420 KB Output is correct
6 Correct 511 ms 7524 KB Output is correct
7 Correct 534 ms 7216 KB Output is correct
8 Correct 534 ms 7360 KB Output is correct
9 Correct 531 ms 7336 KB Output is correct
10 Correct 534 ms 7288 KB Output is correct
11 Correct 529 ms 7244 KB Output is correct
12 Correct 522 ms 7280 KB Output is correct
13 Correct 517 ms 7328 KB Output is correct
14 Correct 516 ms 7232 KB Output is correct
15 Correct 530 ms 7360 KB Output is correct
16 Correct 94 ms 4036 KB Output is correct
17 Correct 102 ms 4004 KB Output is correct
18 Correct 115 ms 4052 KB Output is correct
19 Correct 108 ms 3984 KB Output is correct
20 Correct 98 ms 4068 KB Output is correct
21 Correct 757 ms 6944 KB Output is correct
22 Incorrect 703 ms 6924 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 7244 KB Output is correct
2 Correct 533 ms 7320 KB Output is correct
3 Correct 524 ms 7260 KB Output is correct
4 Correct 515 ms 7360 KB Output is correct
5 Correct 530 ms 7420 KB Output is correct
6 Correct 511 ms 7524 KB Output is correct
7 Correct 534 ms 7216 KB Output is correct
8 Correct 534 ms 7360 KB Output is correct
9 Correct 531 ms 7336 KB Output is correct
10 Correct 534 ms 7288 KB Output is correct
11 Correct 529 ms 7244 KB Output is correct
12 Correct 522 ms 7280 KB Output is correct
13 Correct 517 ms 7328 KB Output is correct
14 Correct 516 ms 7232 KB Output is correct
15 Correct 530 ms 7360 KB Output is correct
16 Correct 94 ms 4036 KB Output is correct
17 Correct 102 ms 4004 KB Output is correct
18 Correct 115 ms 4052 KB Output is correct
19 Correct 108 ms 3984 KB Output is correct
20 Correct 98 ms 4068 KB Output is correct
21 Correct 757 ms 6944 KB Output is correct
22 Incorrect 703 ms 6924 KB Output isn't correct
23 Halted 0 ms 0 KB -