| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 832871 |
2023-08-21T16:07:43 Z |
caganyanmaz |
Boat (APIO16_boat) |
C++17 |
|
302 ms |
524288 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int int64_t
#define pb push_back
using namespace std;
//#define DEBUGGING
#ifdef DEBUGGING
#include "../debug.h"
#else
#define debug(x...) void(42)
#endif
constexpr static int MXN = 6000;
constexpr static int MXR = 11000;
int n;
vector<int> a, b;
vector<int> ranges;
int dp[MXR][MXN]; // Schools passed, last range, count in last range
int old_dp[MXR][MXN];
int sums[MXN][MXN]; // last range
constexpr static int MOD = 1e9 + 7;
static inline int add(int a, int b) { return (a+b) % MOD; }
static inline int mul(int64_t a, int64_t b) { return (a*b) % MOD; }
static inline int pow(int a, int b)
{
int res = 1;
while (b)
{
if (b&1)
{
res = mul(a, res);
b--;
}
else
{
a = mul(a, a);
b >>= 1;
}
}
return res;
}
static inline int _div(int a, int b) { return mul(a, pow(b, MOD-2)); }
int C[MXR][MXN];
int p[MXN];
int32_t main()
{
cin >> n;
p[0] = 1;
for (int i = 1; i < n; i++)
p[i] = mul(i, p[i-1]);
a.resize(n, 0), b.resize(n, 0);
debug("A");
for (int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
b[i]++;
}
debug("b");
vector<int> c;
for (int i = 0; i < n; i++)
c.pb(a[i]);
for (int i = 0; i < n; i++)
c.pb(b[i]);
debug("A");
sort(c.begin(), c.end());
auto last = unique(c.begin(), c.end());
c.erase(last, c.end());
int rn = c.size();
for (int i = 0; i < c.size()-1; i++)
ranges.pb(c[i+1] - c[i]);
debug("B");
for (int i = 0; i < rn; i++)
{
int pf = 1;
for (int j = 0; j <= n; j++)
{
C[i][j] = pf;
pf = mul(pf, ranges[i]-j);
pf = _div(pf, j+1);
if (ranges[i] < j)
C[i][j] = 0;
debug(i, j, C[i][j]);
}
}
debug("D");
debug(a, b);
for (int& i : a)
i = lower_bound(c.begin(), c.end(), i) - c.begin();
for (int& i : b)
i = lower_bound(c.begin(), c.end(), i) - c.begin();
debug(a, b);
for (int j = 0; j < rn; j++)
old_dp[j][0] = 1;
for (int i = 1; i <= n; i++) // Current node
{
for (int j = 0; j < rn; j++) // Current range
{
dp[j][0] = 1;
for (int k = 1; k <= n; k++) // Current count
{
dp[j][k] = 0;
if (a[i-1] <= j && b[i-1] > j)
{
if (j > 0 && k == 1)
dp[j][k] = add(dp[j][k], sums[i-1][j-1]); // Starting with it
dp[j][k] = add(dp[j][k], old_dp[j][k-1]); // Including it
debug(i, j, k);
}
dp[j][k] = add(dp[j][k], old_dp[j][k]); // Not including it
debug(i, j, k, dp[j][k]);
}
}
for (int j = 0; j < rn; j++)
{
if (j > 0)
sums[i][j] = add(sums[i][j], sums[i][j-1]);
debug(sums[i][j]);
for (int k = 1; k <= n; k++)
{
sums[i][j] = add(sums[i][j], mul(dp[j][k], C[j][k]));
}
debug(i, j, sums[i][j]);
}
swap(old_dp, dp);
}
int res = 0;
for (int i = 0; i < rn; i++)
{
for (int j = 1; j <= n; j++)
{
debug(i, j, old_dp[i][j]);
res = add(res, mul(old_dp[i][j], C[i][j]));
}
}
cout << res << "\n";
}
Compilation message
boat.cpp: In function 'int32_t main()':
boat.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (int i = 0; i < c.size()-1; i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
252 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
302 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
