# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
54140 | 2018-07-02T13:04:29 Z | 0^0(#1448) | Linear Garden (IOI08_linear_garden) | C++11 | 149 ms | 9952 KB |
#include <bits/stdc++.h> using namespace std; int n, mod; char str[1000005]; int dp[2][5][5]; vector<pair<int,int> > vec; void get_ans(int idx, int mins, int maxs) { while (idx < n) { if (str[idx] == 'L') { vec.emplace_back(1, 0); mins = min(-1, mins - 1); maxs = max(-1, maxs - 1); } else { vec.emplace_back(min(-1, mins - 1) + 2, max(-1, maxs - 1) + 2); mins = min(1, mins + 1); maxs = max(1, maxs + 1); } idx++; } } int main() { scanf("%d%d%s", &n, &mod, str); for (int i = -2; i <= 2; i++) for (int j = i; j <= 2; j++) dp[n&1][i+2][j+2] = 1; int ans = 1; if (str[0] == 'L') { vec.emplace_back(1, 0); get_ans(1, -1, -1); } else { vec.emplace_back(1, 1); get_ans(1, 1, 1); } assert(vec.size() == n); for (int i = n - 1; i >= 0; i--) { int next = (i + 1) & 1; int now = i & 1; for (int j = -2; j <= 2; j++) for (int k = j; k <= 2; k++) { dp[now][j+2][k+2] = 0; if (j - 1 >= -2)dp[now][j+2][k+2] += dp[next][min(-1, j - 1) + 2][max(-1, k - 1) + 2]; if (k + 1 <= 2)dp[now][j+2][k+2] += dp[next][min(1, j + 1) + 2][max(1, k + 1) + 2]; dp[now][j+2][k+2] %= mod; } int a, b; tie(a, b) = vec[i]; ans = (ans + dp[next][a][b]) % mod; } printf("%d\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 488 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 532 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 556 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 556 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 572 KB | Output is correct |
2 | Correct | 2 ms | 572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 616 KB | Output is correct |
2 | Correct | 2 ms | 620 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 636 KB | Output is correct |
2 | Correct | 3 ms | 636 KB | Output is correct |
3 | Correct | 2 ms | 640 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1020 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1020 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 1272 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 12 ms | 1780 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 5096 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 66 ms | 5228 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 5352 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 92 ms | 9572 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 149 ms | 9952 KB | Output is correct |
2 | Correct | 134 ms | 9952 KB | Output is correct |
3 | Correct | 132 ms | 9952 KB | Output is correct |