# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25545 | 2017-06-23T02:58:23 Z | kajebiii | Boat (APIO16_boat) | C++14 | 6 ms | 4064 KB |
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++) #define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++) #define SZ(v) ((int)(v).size()) #define ALL(v) (v).begin(),(v).end() #define one first #define two second typedef long long ll; typedef pair<int, int> pi; const int INF = 0x3f2f1f0f; const ll LINF = 1ll * INF * INF; const int MAX_N = 5e2 + 10, MAX_C = MAX_N * 2, MOD = 1e9 + 7; int N, Nr[MAX_N][2], Dy[MAX_N][MAX_C], Sum[MAX_C]; vector<int> Co; int main() { cin >> N; REPO(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Nr[i][j] += j, Co.push_back(Nr[i][j]); Co.push_back(0); sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end()); REPO(i, N) REP(j, 2) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin(); int cN = SZ(Co); Dy[0][0] = 1; REPO(i, N) { for(int j=0; j+1<cN; j++) { if(j) Sum[j] = Sum[j-1]; else Sum[j] = 0; Sum[j] = (Sum[j] + Dy[i-1][j]) % MOD; } for(int j=0; j<cN; j++) Dy[i][j] = Dy[i-1][j]; for(int j=Nr[i][0]; j<Nr[i][1]; j++) Dy[i][j] = (Dy[i][j] + 1ll * Sum[j-1] * (Co[j+1] - Co[j]) ) % MOD; } int ans = 0; for(int j=0; j<cN; j++) ans = (ans + Dy[N][j]) % MOD; ans = (ans + MOD - 1) % MOD; printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4064 KB | Output is correct |
2 | Correct | 3 ms | 4064 KB | Output is correct |
3 | Correct | 3 ms | 4064 KB | Output is correct |
4 | Correct | 3 ms | 4064 KB | Output is correct |
5 | Correct | 6 ms | 4064 KB | Output is correct |
6 | Correct | 3 ms | 4064 KB | Output is correct |
7 | Correct | 3 ms | 4064 KB | Output is correct |
8 | Correct | 6 ms | 4064 KB | Output is correct |
9 | Correct | 3 ms | 4064 KB | Output is correct |
10 | Correct | 3 ms | 4064 KB | Output is correct |
11 | Correct | 3 ms | 4064 KB | Output is correct |
12 | Correct | 3 ms | 4064 KB | Output is correct |
13 | Correct | 3 ms | 4064 KB | Output is correct |
14 | Correct | 3 ms | 4064 KB | Output is correct |
15 | Correct | 3 ms | 4064 KB | Output is correct |
16 | Correct | 0 ms | 4064 KB | Output is correct |
17 | Correct | 0 ms | 4064 KB | Output is correct |
18 | Correct | 0 ms | 4064 KB | Output is correct |
19 | Correct | 0 ms | 4064 KB | Output is correct |
20 | Correct | 0 ms | 4064 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4064 KB | Output is correct |
2 | Correct | 3 ms | 4064 KB | Output is correct |
3 | Correct | 3 ms | 4064 KB | Output is correct |
4 | Correct | 3 ms | 4064 KB | Output is correct |
5 | Correct | 6 ms | 4064 KB | Output is correct |
6 | Correct | 3 ms | 4064 KB | Output is correct |
7 | Correct | 3 ms | 4064 KB | Output is correct |
8 | Correct | 6 ms | 4064 KB | Output is correct |
9 | Correct | 3 ms | 4064 KB | Output is correct |
10 | Correct | 3 ms | 4064 KB | Output is correct |
11 | Correct | 3 ms | 4064 KB | Output is correct |
12 | Correct | 3 ms | 4064 KB | Output is correct |
13 | Correct | 3 ms | 4064 KB | Output is correct |
14 | Correct | 3 ms | 4064 KB | Output is correct |
15 | Correct | 3 ms | 4064 KB | Output is correct |
16 | Correct | 0 ms | 4064 KB | Output is correct |
17 | Correct | 0 ms | 4064 KB | Output is correct |
18 | Correct | 0 ms | 4064 KB | Output is correct |
19 | Correct | 0 ms | 4064 KB | Output is correct |
20 | Correct | 0 ms | 4064 KB | Output is correct |
21 | Incorrect | 3 ms | 4064 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 4064 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 4064 KB | Output is correct |
2 | Correct | 3 ms | 4064 KB | Output is correct |
3 | Correct | 3 ms | 4064 KB | Output is correct |
4 | Correct | 3 ms | 4064 KB | Output is correct |
5 | Correct | 6 ms | 4064 KB | Output is correct |
6 | Correct | 3 ms | 4064 KB | Output is correct |
7 | Correct | 3 ms | 4064 KB | Output is correct |
8 | Correct | 6 ms | 4064 KB | Output is correct |
9 | Correct | 3 ms | 4064 KB | Output is correct |
10 | Correct | 3 ms | 4064 KB | Output is correct |
11 | Correct | 3 ms | 4064 KB | Output is correct |
12 | Correct | 3 ms | 4064 KB | Output is correct |
13 | Correct | 3 ms | 4064 KB | Output is correct |
14 | Correct | 3 ms | 4064 KB | Output is correct |
15 | Correct | 3 ms | 4064 KB | Output is correct |
16 | Correct | 0 ms | 4064 KB | Output is correct |
17 | Correct | 0 ms | 4064 KB | Output is correct |
18 | Correct | 0 ms | 4064 KB | Output is correct |
19 | Correct | 0 ms | 4064 KB | Output is correct |
20 | Correct | 0 ms | 4064 KB | Output is correct |
21 | Incorrect | 3 ms | 4064 KB | Output isn't correct |
22 | Halted | 0 ms | 0 KB | - |