Submission #1263256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263256		DeltaStruct	Linear Garden (IOI08_linear_garden)	C++17	100 / 100	585 ms	2304 KiB

linear_garden

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

int main(){
  int n,m; cin >> n >> m; string s; cin >> s;
  vector dp(3,vector(3,vector(5,vector<int>(2)))),res = dp;
  ++res[0][0][2][1] %= m;
  for (int i(0);i < n;++i){
    dp = res;
    for (int a(0);a < 3;++a) for (int b(0);b < 3;++b) for (int c(0);c < 5;++c) res[a][b][c][0] = res[a][b][c][1] = 0;
    for (int a(0);a < 3;++a) for (int b(0);b < 3;++b) for (int c(0);c < 5;++c) for (int d(0);d < 2;++d){
      if (c+1<5) (res[max(a,c-1)][b][c+1][d&&s[i]=='L'] += dp[a][b][c][d]) %= m;
      if ((!d||s[i]=='P')&&c-1>=0) (res[a][max(b,3-c)][c-1][d&&s[i]=='P'] += dp[a][b][c][d]) %= m;
    }
    for (int a(0);a < 3;++a) for (int b(0);b < 3;++b) if (a+b>=3) for (int c(0);c < 5;++c){
      res[a][b][c][0] = res[a][b][c][1] = 0;
    }
  }
  int r = 0;
  for (int a(0);a < 3;++a) for (int b(0);b < 3;++b) for (int c(0);c < 5;++c) r += res[a][b][c][0]+res[a][b][c][1];
  cout << r%m << endl;
}

• 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