Submission #54084

#	Time	Username	Problem	Language	Result	Execution time	Memory
54084		imeimi2000	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	215 ms	9596 KiB

linear_garden

#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 (stderr)

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 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5