Submission #988703

#	Time	Username	Problem	Language	Result	Execution time	Memory
988703		MilosMilutinovic	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	403 ms	8940 KiB

linear_garden

/**
 *    author:  wxhtzdy
 *    created: 21.07.2022 09:22:25
**/
#include <bits/stdc++.h>
 
using namespace std;
 
int md;
 
int add(int a, int b) {
  return a + b >= md ? a + b - md : a + b;
}
 
int mul(int a, int b) {
  return a * 1LL * b % md;
}

int f[5][5][5], new_f[5][5][5];
vector<int> qs[5][5][5];
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n >> md;
  string s;
  cin >> s;              
  int bal = 2; 
  int mn = 2, mx = 2;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'P' && bal > 0 && bal - 1 - min(mn, bal - 1) <= 2 && max(mx, bal - 1) - (bal - 1) <= 2) {
      qs[bal - 1][min(mn, bal - 1)][max(mx, bal - 1)].push_back(n - i - 1);
    }
    bal += (s[i] == 'P' ? +1 : -1);
    mn = min(mn, bal);
    mx = max(mx, bal);
  }
  vector<int> cnt(n + 1);
  int ans = 1;
  for (int st = 0; st < 5; ++st) {
    for (int st_mn = 0; st_mn <= st; ++st_mn) {
      for (int st_mx = st; st_mx < 5; ++st_mx) {
        int limit = -1;
        for (auto &p : qs[st][st_mn][st_mx]) {
          cnt[p] += 1;
          limit = max(limit, p);
        }                           
        for (int A = 0; A < 5; ++A) {
          for (int B = 0; B < 5; ++B) {
            for (int C = 0; C < 5; ++C) {
              f[A][B][C] = 0;
            }
          }
        }
        f[st][st_mn][st_mx] = 1;
        for (int i = 0; i <= limit; ++i) {
          for (int bal = 0; bal < 5; ++bal) {
            for (int mn = 0; mn <= min(st_mn, bal); ++mn) {
              for (int mx = max(st_mx, bal); mx < 5; ++mx) {
                if (f[bal][mn][mx] == 0) {
                  continue;
                }
                ans = add(ans, mul(cnt[i], f[bal][mn][mx]));
                for (int d = -1; d <= 1; d += 2) {
                  int new_bal = bal + d;
                  if (new_bal >= 0 && new_bal < 5) {
                    int new_mn = min(mn, new_bal);
                    int new_mx = max(mx, new_bal);
                    if (new_bal - new_mn <= 2 && new_mx - new_bal <= 2) {
                      new_f[new_bal][new_mn][new_mx] = add(new_f[new_bal][new_mn][new_mx], f[bal][mn][mx]);
                    }
                  }
                }
              }
            }
          }
          for (int A = 0; A < 5; ++A) {
            for (int B = 0; B < 5; ++B) {
              for (int C = 0; C < 5; ++C) {
                f[A][B][C] = new_f[A][B][C];
                new_f[A][B][C] = 0;
              }
            }
          }
          cnt[i] = 0;
        }              
      }
    }
  }
  cout << ans << '\n';
  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