oj.uz

답안 #637504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637504 2022-09-02T10:24:33 Z lto5 Linear Garden (IOI08_linear_garden) C++14
0 / 100
 35 ms 65536 KB 
#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] == 'B') {
      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] == 'A' ? 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;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:58:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   freopen("garden.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:59:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   freopen("garden.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 35 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #22
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #23
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -