Submission #1263648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263648		kunzaZa183	Linear Garden (IOI08_linear_garden)	C++20	95 / 100	94 ms	71736 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mn = 1e6, smth = 3;
int dp[mn][smth][smth];
signed main() {
  int n, mod;
  cin >> n >> mod;
  string s;
  cin >> s;

  dp[0][0][0] = 1;
  // l then p
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < smth; j++) {
      for (int k = 0; k < smth; k++) {
        if (j != 2) {
          dp[i + 1][j + 1][max(0ll, k - 1)] += dp[i][j][k];
          dp[i + 1][j + 1][max(0ll, k - 1)] %= mod;
        }
        if (k != 2) {
          dp[i + 1][max(0ll, j - 1)][k + 1] += dp[i][j][k];
          dp[i + 1][max(0ll, j - 1)][k + 1] %= mod;
        }
      }
    }
  }

  int ls = 0, ps = 0;
  int prev = 0;
  for (int i = 0; i < n; i++) {
    // cout << i << " " << prev << " " << ls << " " << ps << "\n";
    if (s[i] == 'P') {

      for (int j = 0; j + ls + 1 < smth; j++)
        for (int k = 0; k + max(0ll, ps - 1) < smth; k++) {
          prev += dp[n - i - 1][j][k];
          prev %= mod;
        }

      ps++;
      ls--;
      ls = max(ls, 0ll);
    } else {
      ps--;
      ls++;

      ps = max(ps, 0ll);
    }
  }

  // for (int i = 0; i < smth; i++)
  //   for (int j = 0; j < smth; j++)
  //     cout << i << " " << j << " " << dp[3][i][j] << "\n";

  cout << (prev + 1) % mod << "\n";
}

• 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: 0 / 5