Submission #320125

#	Time	Username	Problem	Language	Result	Execution time	Memory
320125		AlexLuchianov	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	287 ms	3424 KiB

linear_garden

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int dp[3][3][5][2];
int dp2[3][3][5][2];

int main() {
  int n, modulo;
  std::cin >> n >> modulo;
  std::string s;
  std::cin >> s;
  s = "#" + s;

  int result = 0;
  dp[0][0][2][0] = 1;

  for(int i = 1;i <= n; i++) {
    int val = 0;
    if(s[i] == 'P')
      val = 1;

    for(int smin = 0; smin <= 2; smin++)
      for(int smax = 0; smax <= 2 - smin; smax++)
        for(int curr = 2 - smin; curr <= 2 + smax; curr++)
          for(int h = 0; h < 2; h++) {
            for(int h2 = 0; h2 < 2 && (h == 1 || h2 <= val); h2++) {
              int smax2 = smax;
              int smin2 = smin;
              int curr2 = curr + h2 * 2 - 1;
              smin2 = std::max(smin2, -(curr2 - 2));
              smax2 = std::max(smax2, curr2 - 2);
              
              if(smin2 + smax2 <= 2) {
                dp2[smin2][smax2][curr2][h | (h2 < val)] += dp[smin][smax][curr][h];
                if(modulo <= dp2[smin2][smax2][curr2][h | (h2 < val)])
                  dp2[smin2][smax2][curr2][h | (h2 < val)] -= modulo;
              }
            }
          }
    for(int smin = 0; smin <= 2; smin++)
      for(int smax = 0; smax <= 2 - smin; smax++)
        for(int curr = 2 - smin; curr <= 2 + smax; curr++) {
          for(int h = 0; h < 2; h++) {
            dp[smin][smax][curr][h] = dp2[smin][smax][curr][h];
            dp2[smin][smax][curr][h] = 0;
            if(i == n && h == 1) {
              result += dp[smin][smax][curr][h];
              if(modulo <= result)
                result -= modulo;
            }
          }
        }
  }
  std::cout << (result + 1) % modulo;
  return 0;
}

• 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