# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
98627 | 2019-02-25T02:08:16 Z | PeppaPig | Linear Garden (IOI08_linear_garden) | C++14 | 351 ms | 14080 KB |
#include <bits/stdc++.h> #define long long long using namespace std; const int N = 1e6+5; int n, m, mx[N], mn[N], cur[N]; long dp[2][3][3][5], ans = 1; char A[N]; int main() { scanf("%d %d", &n, &m); scanf(" %s", A+1); for(int i = 1; i <= n; i++) { mx[i] = mx[i - 1], mn[i] = mn[i - 1], cur[i] = cur[i - 1]; if(A[i] == 'L') ++cur[i]; else --cur[i]; mx[i] = max(mx[i], cur[i]), mn[i] = min(mn[i], cur[i]); } for(int i = n; i; i--) { int now = i & 1, pre = now ^ 1; for(int a = 0; a <= 2; a++) for(int b = -2; b <= 0; b++) for(int x = -2; x <= 2; x++) { dp[now][a][2 + b][2 + x] = 0; if(a - b > 2 || x < b || x > a) continue; if(i == n) dp[now][a][2+b][2+x] = 1; else { if(x < 2 && max(a, x + 1) - b <= 2) dp[now][a][2 + b][2 + x] += dp[pre][max(a, x + 1)][2 + b][3 + x]; if(x > -2 && a - min(b, x - 1) <= 2) dp[now][a][2 + b][2 + x] += dp[pre][a][2 + min(b, x - 1)][1 + x]; dp[now][a][2 + b][2 + x] %= m; } } if(A[i] == 'P') { int x = cur[i - 1] + 1, a = max(mx[i - 1], x), b = min(mn[i - 1], x); if(x <= 2 && a - b <= 2) { if(i == n) ++ans; else ans += dp[now][a][2 + b][2 + x]; ans %= m; } } } printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 356 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 384 KB | Output is correct |
2 | Correct | 2 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 384 KB | Output is correct |
2 | Correct | 3 ms | 384 KB | Output is correct |
3 | Correct | 3 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 21 ms | 1152 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 1280 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 97 ms | 4628 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 144 ms | 5888 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 162 ms | 7392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 235 ms | 8936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 343 ms | 14080 KB | Output is correct |
2 | Correct | 351 ms | 14072 KB | Output is correct |
3 | Correct | 324 ms | 14080 KB | Output is correct |