제출 #637505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637505		lto5	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	41 ms	65536 KiB

linear_garden

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)

int n, mod;
string s;

int f[1000001][5][16];
int id[5][5], cnt_id;

// -2 -1 0 1 2
// 0 1 2 3 4

#define offset(x) (x + 2)

void add_mod (int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}

int add (int a, int b) {
  add_mod(a, b);
  return a;
}

int dp (int idx, int pre, int min_pre, int max_pre) {
  if (abs(pre) > 2 || min_pre > max_pre)
    return 0;
  if (idx > n) {
    return 1;
  }

  int &ans = f[idx][offset(pre)][id[offset(min_pre)][offset(max_pre)]];

  if (ans != -1)
    return ans;

  ans = 0;

  int new_pre = pre + 1;
  if (abs(new_pre) <= 2 && min_pre >= new_pre - 2 && max_pre <= new_pre + 2) {
    add_mod(ans, dp(idx + 1, new_pre, min(min_pre, new_pre), max(max_pre, new_pre)));
  }
  new_pre = pre - 1;
  if (abs(new_pre) <= 2 && min_pre >= new_pre - 2 && max_pre <= new_pre + 2) {
    add_mod(ans, dp(idx + 1, new_pre, min(min_pre, new_pre), max(max_pre, new_pre)));
  }

  return ans;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  //freopen("garden.inp", "r", stdin);
  //freopen("garden.out", "w", stdout);

  cin >> n >> mod >> s;
  s = ' ' + s;

  for (int i = 0; i <= 4; i++)
    for (int j = i; j <= 4; j++) {
      id[i][j] = cnt_id++;
    }

  memset(f, -1, sizeof(f));

  int ans = 0;
  int cur_pre = 0, min_pre = 0, max_pre = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'P') {
      int tmp_pre = cur_pre + 1;
      int tmp_min = min(min_pre, tmp_pre);
      int tmp_max = max(max_pre, tmp_pre);
      if (abs(tmp_pre) <= 2 && min_pre >= tmp_pre - 2 && max_pre <= tmp_pre + 2)
        add_mod(ans, dp(i + 1, tmp_pre, tmp_min, tmp_max));
    }
    cur_pre += s[i] == 'L' ? 1 : -1;
    min_pre = min(min_pre, cur_pre);
    max_pre = max(max_pre, cur_pre);
  }
  cout << add(ans, 1);

//  f[0][offset(0)][id[offset(0)][offset(0)]] = 1;
//
//  for (int i = 0; i < n; i++) {
//    for (int last_pre = -2; last_pre <= 2; last_pre++) {
//      for (int min_pre = -2; min_pre <= 2; min_pre++) {
//        for (int max_pre = min_pre; max_pre <= 2; max_pre++) {
//          int last_id = id[offset(min_pre)][offset(max_pre)];
//          int last_dp = f[i][offset(last_pre)][last_id];
//
//          if (last_dp == 0)
//            continue;
//
//          int new_pre = last_pre + 1;
//          if (abs(new_pre) <= 2 && min_pre >= new_pre - 2 && max_pre <= new_pre + 2) {
//            int next_min = min(min_pre, new_pre);
//            int next_max = max(max_pre, new_pre);
//
//            add_mod(f[i + 1][offset(new_pre)][id[offset(next_min)][offset(next_max)]], last_dp);
//          }
//
//          new_pre = last_pre - 1;
//          if (abs(new_pre) <= 2 && min_pre >= new_pre - 2 && max_pre <= new_pre + 2) {
//            int next_min = min(min_pre, new_pre);
//            int next_max = max(max_pre, new_pre);
//
//            add_mod(f[i + 1][offset(new_pre)][id[offset(next_min)][offset(next_max)]], last_dp);
//          }
//        }
//      }
//    }
//  }
//
//  int ans = 0;
//  for (int last_pre = -2; last_pre <= 2; last_pre++)
//    for (int i = 0; i < cnt_id; i++) {
//      add_mod(ans, f[n][offset(last_pre)][i]);
//    }
//  cout << ans;
  return 0;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5