# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
39826 | 2018-01-20T05:38:32 Z | 14kg | Boat (APIO16_boat) | C++11 | 6 ms | 13092 KB |
#include <stdio.h> #include <set> #include <algorithm> #include <map> #define N 501 #define INF 2000000000 #define MOD 1000000007 using namespace std; int n, r_len, L[N][N * 4]; long long dp[N][N * 4]; pair<int, int> in[N], r[N * 4]; set<int> S; map<int, int> M; void r_push(int x, int y) { if (x > y) return; r[++r_len] = { x,y }; if (x == y) M[x] = r_len; } int main() { int path = 0; long long sum; // freopen("input.txt", "r", stdin); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d", &in[i].first, &in[i].second); S.insert(in[i].first), S.insert(in[i].second); } for (auto i : S) r_push(path + 1, i - 1), r_push(i, i), path = i; for (int i = 1; i <= n; i++) in[i] = { M[in[i].first],M[in[i].second] }; dp[0][0] = 1; for (int i = 1; i <= n; i++) { sum = dp[i][0] = 1; for (int j = 1; j <= r_len; j++) { dp[i][j] = dp[i - 1][j]; if (in[i].first <= j && j <= in[i].second) { dp[i][j] += sum * (long long)(r[j].second - r[j].first + 1); if (!L[i - 1][j]) L[i][j] = i - 1; else { L[i][j] = L[i - 1][j]; long long len_x = i - (long long)L[i][i], len_y = (long long)(r[j].second - r[j].first + 1); long long P = (len_x + len_y - 1)*(len_x + len_y - 2) / 2 - (len_x + len_y - 2)*(len_x + len_y - 3) / 2; dp[i][j] += dp[L[i][j]][j - 1] * P; } dp[i][j] %= MOD; } sum = (sum + dp[i - 1][j]) % MOD; } } sum = 0; for (int i = 1; i <= r_len; i++) sum = (sum + dp[n][i]) % MOD; printf("%lld", sum); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12960 KB | Output is correct |
2 | Correct | 0 ms | 12960 KB | Output is correct |
3 | Correct | 1 ms | 12960 KB | Output is correct |
4 | Correct | 5 ms | 12960 KB | Output is correct |
5 | Correct | 2 ms | 12960 KB | Output is correct |
6 | Correct | 0 ms | 12960 KB | Output is correct |
7 | Correct | 2 ms | 12960 KB | Output is correct |
8 | Correct | 4 ms | 12960 KB | Output is correct |
9 | Correct | 3 ms | 12960 KB | Output is correct |
10 | Correct | 4 ms | 12960 KB | Output is correct |
11 | Correct | 0 ms | 12960 KB | Output is correct |
12 | Correct | 4 ms | 12960 KB | Output is correct |
13 | Correct | 4 ms | 12960 KB | Output is correct |
14 | Correct | 3 ms | 12960 KB | Output is correct |
15 | Correct | 4 ms | 12960 KB | Output is correct |
16 | Correct | 3 ms | 12960 KB | Output is correct |
17 | Correct | 0 ms | 12960 KB | Output is correct |
18 | Correct | 0 ms | 12960 KB | Output is correct |
19 | Correct | 0 ms | 12960 KB | Output is correct |
20 | Correct | 0 ms | 12960 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12960 KB | Output is correct |
2 | Correct | 0 ms | 12960 KB | Output is correct |
3 | Correct | 1 ms | 12960 KB | Output is correct |
4 | Correct | 5 ms | 12960 KB | Output is correct |
5 | Correct | 2 ms | 12960 KB | Output is correct |
6 | Correct | 0 ms | 12960 KB | Output is correct |
7 | Correct | 2 ms | 12960 KB | Output is correct |
8 | Correct | 4 ms | 12960 KB | Output is correct |
9 | Correct | 3 ms | 12960 KB | Output is correct |
10 | Correct | 4 ms | 12960 KB | Output is correct |
11 | Correct | 0 ms | 12960 KB | Output is correct |
12 | Correct | 4 ms | 12960 KB | Output is correct |
13 | Correct | 4 ms | 12960 KB | Output is correct |
14 | Correct | 3 ms | 12960 KB | Output is correct |
15 | Correct | 4 ms | 12960 KB | Output is correct |
16 | Correct | 3 ms | 12960 KB | Output is correct |
17 | Correct | 0 ms | 12960 KB | Output is correct |
18 | Correct | 0 ms | 12960 KB | Output is correct |
19 | Correct | 0 ms | 12960 KB | Output is correct |
20 | Correct | 0 ms | 12960 KB | Output is correct |
21 | Incorrect | 6 ms | 13092 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 12960 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12960 KB | Output is correct |
2 | Correct | 0 ms | 12960 KB | Output is correct |
3 | Correct | 1 ms | 12960 KB | Output is correct |
4 | Correct | 5 ms | 12960 KB | Output is correct |
5 | Correct | 2 ms | 12960 KB | Output is correct |
6 | Correct | 0 ms | 12960 KB | Output is correct |
7 | Correct | 2 ms | 12960 KB | Output is correct |
8 | Correct | 4 ms | 12960 KB | Output is correct |
9 | Correct | 3 ms | 12960 KB | Output is correct |
10 | Correct | 4 ms | 12960 KB | Output is correct |
11 | Correct | 0 ms | 12960 KB | Output is correct |
12 | Correct | 4 ms | 12960 KB | Output is correct |
13 | Correct | 4 ms | 12960 KB | Output is correct |
14 | Correct | 3 ms | 12960 KB | Output is correct |
15 | Correct | 4 ms | 12960 KB | Output is correct |
16 | Correct | 3 ms | 12960 KB | Output is correct |
17 | Correct | 0 ms | 12960 KB | Output is correct |
18 | Correct | 0 ms | 12960 KB | Output is correct |
19 | Correct | 0 ms | 12960 KB | Output is correct |
20 | Correct | 0 ms | 12960 KB | Output is correct |
21 | Incorrect | 6 ms | 13092 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |