Submission #600845

#	Time	Username	Problem	Language	Result	Execution time	Memory
600845		MilosMilutinovic	Linear Garden (IOI08_linear_garden)	C++17	85 / 100	1573 ms	7012 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 main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n;
  cin >> n >> md;
  string s;
  cin >> s;              
  int bal = 2; 
  vector<vector<vector<vector<int>>>> qs(5, vector<vector<vector<int>>>(5, vector<vector<int>>(5)));
  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);
        }                           
        vector<vector<vector<int>>> f(5, vector<vector<int>>(5, vector<int>(5)));
        f[st][st_mn][st_mx] = 1;
        for (int i = 0; i <= limit; i++) {
          vector<vector<vector<int>>> new_f(5, vector<vector<int>>(5, vector<int>(5)));
          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]);
                    }
                  }
                }
              }
            }
          }
          cnt[i] = 0;
          swap(f, new_f);
        }              
      }
    }
  }
  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: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5