oj.uz

답안 #54084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54084 2018-07-02T09:52:23 Z imeimi2000 Linear Garden (IOI08_linear_garden) C++17
100 / 100
 215 ms 9596 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, mod;
char str[1000001];
int dp1[5][5][5];
int dp2[5][5][5];
int mx[1000001];
int mn[1000001];
int main() {
    scanf("%d%d%s", &n, &mod, str);
    int sum = 0, mxx = 0, mnx = 0;
    for (int i = 0; i < n; ++i) {
        --sum;
        mx[i] = max(mxx - sum, 0);
        mn[i] = min(mnx - sum, 0);
        if (str[i] == 'P') sum += 2;
        mxx = max(mxx, sum);
        mnx = min(mnx, sum);
    }
    dp1[2][2][2] = 1;
    int ans = 1;
    for (int i = n; i--; ) {
        if (str[i] == 'P') {
            for (int j = 0; j <= 2; ++j) {
                for (int k = 2; k <= j + 2; ++k) {
                    for (int l = j; l <= k; ++l) {
                        if (max(k, l + mx[i]) - min(j, l + mn[i]) <= 2) {
                            ans += dp1[j][k][l];
                            ans %= mod;
                        }
                    }
                }
            }
        }
        for (int j = 0; j <= 2; ++j) {
            for (int k = 2; k <= j + 2; ++k) {
                for (int l = j; l <= k; ++l) {
                    if (l < 4)
                        dp2[j][max(k, l + 1)][l + 1] += dp1[j][k][l];
                    if (l > 0)
                        dp2[min(j, l - 1)][k][l - 1] += dp1[j][k][l];
                }
            }
        }
        for (int j = 0; j <= 2; ++j) {
            for (int k = 2; k <= j + 2; ++k) {
                for (int l = j; l <= k; ++l) {
                    dp1[j][k][l] = dp2[j][k][l] % mod;
                    dp2[j][k][l] = 0;
                }
            }
        }
    }
    printf("%d\n", ans);
	return 0;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%s", &n, &mod, str);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 496 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 496 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 496 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #7
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #9
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 704 KB Output is correct

Subtask #10
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #11
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct

Subtask #12
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #13
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 704 KB Output is correct
2 Correct 3 ms 704 KB Output is correct
3 Correct 3 ms 704 KB Output is correct

Subtask #15
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 824 KB Output is correct

Subtask #16
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 880 KB Output is correct

Subtask #17
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1252 KB Output is correct

Subtask #18
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 1456 KB Output is correct

Subtask #19
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 3620 KB Output is correct

Subtask #20
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 4348 KB Output is correct

Subtask #21
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 5284 KB Output is correct

Subtask #22
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 6320 KB Output is correct

Subtask #23
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 9596 KB Output is correct
2 Correct 203 ms 9596 KB Output is correct
3 Correct 210 ms 9596 KB Output is correct