oj.uz

Submission #53959

# Submission time Handle Problem Language Result Execution time Memory
53959 2018-07-02T05:22:24 Z 강태규(#1453) Linear Garden (IOI08_linear_garden) C++11
80 / 100
 169 ms 9428 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[3][5][5];
int dp2[3][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);
        mn[i] = min(mnx, sum);
        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 < 3; ++j) {
                for (int k = max(j, 2); k <= j + 2; ++k) {
                    for (int l = j; l <= k; ++l) {
                        if (0 <= l + mn[i] && l + mx[i] <= 4 && max(k, l + mx[i]) - min(j, l + mn[i]) <= 2) {
                            ans += dp1[j][k][l];
                            ans %= mod;
                        }
                    }
                }
            }
        }
        for (int j = 0; j < 3; ++j) {
            for (int k = max(j, 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 < 3; ++j) {
            for (int k = max(j, 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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 412 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 412 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 636 KB Output is correct
2 Incorrect 2 ms 636 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Incorrect 3 ms 636 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 764 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 764 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1148 KB Output isn't correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1276 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3324 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4092 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 5152 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 6012 KB Output is correct

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 9428 KB Output isn't correct
2 Halted 0 ms 0 KB -