| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 39828 | 2018-01-20T05:42:36 Z | 14kg | Boat (APIO16_boat) | C++11 | 8 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][j], len_y = (long long)(r[j].second - r[j].first + 1);
long long P = (len_x + len_y)*(len_x + len_y - 1) / 2 - (len_x + len_y - 1)*(len_x + len_y - 2) / 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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 12960 KB | Output is correct |
| 2 | Correct | 6 ms | 12960 KB | Output is correct |
| 3 | Correct | 5 ms | 12960 KB | Output is correct |
| 4 | Correct | 4 ms | 12960 KB | Output is correct |
| 5 | Correct | 2 ms | 12960 KB | Output is correct |
| 6 | Correct | 2 ms | 12960 KB | Output is correct |
| 7 | Correct | 0 ms | 12960 KB | Output is correct |
| 8 | Correct | 0 ms | 12960 KB | Output is correct |
| 9 | Correct | 8 ms | 12960 KB | Output is correct |
| 10 | Correct | 4 ms | 12960 KB | Output is correct |
| 11 | Correct | 3 ms | 12960 KB | Output is correct |
| 12 | Correct | 3 ms | 12960 KB | Output is correct |
| 13 | Correct | 4 ms | 12960 KB | Output is correct |
| 14 | Correct | 0 ms | 12960 KB | Output is correct |
| 15 | Correct | 0 ms | 12960 KB | Output is correct |
| 16 | Correct | 0 ms | 12960 KB | Output is correct |
| 17 | Correct | 2 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 |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 12960 KB | Output is correct |
| 2 | Correct | 6 ms | 12960 KB | Output is correct |
| 3 | Correct | 5 ms | 12960 KB | Output is correct |
| 4 | Correct | 4 ms | 12960 KB | Output is correct |
| 5 | Correct | 2 ms | 12960 KB | Output is correct |
| 6 | Correct | 2 ms | 12960 KB | Output is correct |
| 7 | Correct | 0 ms | 12960 KB | Output is correct |
| 8 | Correct | 0 ms | 12960 KB | Output is correct |
| 9 | Correct | 8 ms | 12960 KB | Output is correct |
| 10 | Correct | 4 ms | 12960 KB | Output is correct |
| 11 | Correct | 3 ms | 12960 KB | Output is correct |
| 12 | Correct | 3 ms | 12960 KB | Output is correct |
| 13 | Correct | 4 ms | 12960 KB | Output is correct |
| 14 | Correct | 0 ms | 12960 KB | Output is correct |
| 15 | Correct | 0 ms | 12960 KB | Output is correct |
| 16 | Correct | 0 ms | 12960 KB | Output is correct |
| 17 | Correct | 2 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 | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 12960 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 12960 KB | Output is correct |
| 2 | Correct | 6 ms | 12960 KB | Output is correct |
| 3 | Correct | 5 ms | 12960 KB | Output is correct |
| 4 | Correct | 4 ms | 12960 KB | Output is correct |
| 5 | Correct | 2 ms | 12960 KB | Output is correct |
| 6 | Correct | 2 ms | 12960 KB | Output is correct |
| 7 | Correct | 0 ms | 12960 KB | Output is correct |
| 8 | Correct | 0 ms | 12960 KB | Output is correct |
| 9 | Correct | 8 ms | 12960 KB | Output is correct |
| 10 | Correct | 4 ms | 12960 KB | Output is correct |
| 11 | Correct | 3 ms | 12960 KB | Output is correct |
| 12 | Correct | 3 ms | 12960 KB | Output is correct |
| 13 | Correct | 4 ms | 12960 KB | Output is correct |
| 14 | Correct | 0 ms | 12960 KB | Output is correct |
| 15 | Correct | 0 ms | 12960 KB | Output is correct |
| 16 | Correct | 0 ms | 12960 KB | Output is correct |
| 17 | Correct | 2 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 | - |