| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 63226 |
2018-08-01T06:31:17 Z |
kingpig9 |
Boat (APIO16_boat) |
C++11 |
|
10 ms |
4600 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 510, MOD = 1e9 + 7;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
inline void addeq (int &x, int y) {
x += y;
if (x >= MOD) {
x -= MOD;
}
}
inline int add (int x, int y) {
addeq(x, y);
return x;
}
inline int subtr (int x, int y) {
x -= y;
if (x < 0) {
x += MOD;
}
return x;
}
inline int mult (int x, int y) {
return ll(x) * y % MOD;
}
inline void multeq (int &x, int y) {
x = mult(x, y);
}
int N;
int A[MAXN], B[MAXN];
int inda[MAXN], indb[MAXN];
vector<int> vals;
int len[MAXN];
int dp[MAXN][2 * MAXN]; //dp[position][Where is your thing?]
int pdp[MAXN][2 * MAXN];
int inv[MAXN];
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d %d", &A[i], &B[i]);
B[i]++;
vals.push_back(A[i]);
vals.push_back(B[i]);
}
sort(all(vals));
vals.resize(unique(all(vals)) - vals.begin());
for (int i = 1; i <= N; i++) {
A[i] = lower_bound(all(vals), A[i]) - vals.begin();
B[i] = lower_bound(all(vals), B[i]) - vals.begin();
}
for (int i = 1; i < vals.size(); i++) {
len[i] = vals[i] - vals[i - 1];
}
inv[1] = 1;
for (int i = 2; i < MAXN; i++) {
inv[i] = mult(inv[MOD % i], MOD - MOD / i);
}
for (int i = 0; i < vals.size(); i++) {
dp[0][i] = 1;
}
for (int i = 0; i < vals.size(); i++) {
dp[0][i] = 1;
}
for (int i = 1; i <= N; i++) {
for (int j = A[i] + 1; j <= B[i]; j++) {
dp[i][j] = mult(len[j], dp[i - 1][j - 1]);
int cho = len[j] - 1;
for (int k = i - 1; k >= 1; k--) {
if (A[k] + 1 <= j && j <= B[k]) {
int npos = i - k + 1;
multeq(cho, mult(len[j] + npos - 2, inv[npos])); //did thru examples...not as clear at first, but you will understand.
if (cho == 0) {
break;
}
addeq(dp[i][j], mult(cho, dp[k - 1][j - 1]));
}
}
}
dp[i][0] = 1;
for (int j = 1; j < vals.size(); j++) {
addeq(dp[i][j], subtr(add(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]));
}
}
printf("%d\n", subtr(dp[N][vals.size() - 1], 1));
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < vals.size(); i++) {
~~^~~~~~~~~~~~~
boat.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vals.size(); i++) {
~~^~~~~~~~~~~~~
boat.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vals.size(); i++) {
~~^~~~~~~~~~~~~
boat.cpp:102:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 1; j < vals.size(); j++) {
~~^~~~~~~~~~~~~
boat.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
boat.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &A[i], &B[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
4600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
4600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
4600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
