Submission #235590

#	Time	Username	Problem	Language	Result	Execution time	Memory
235590		Haunted_Cpp	Linear Garden (IOI08_linear_garden)	C++17	0 / 100	51 ms	65540 KiB

linear_garden

/**
 *  author: Duarte Nobrega
 *  created: 28.05.2020    
**/

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

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

const int N = 1e6 + 5;

int dp [N][5][5][3], n, MOD;

string w;

int add (int a, int b) {
  int res = a + b;
  if (res >= MOD) res -= MOD;
  return res;
}

int calc (int estado, char cur, char is) {
  if (estado > 0) return estado;
  if (cur < is) return 1;
  if (cur > is) return 2;
  return 0;
}

int solve (int p = 0, int maior = 2, int menor = 2, int estado = 0) {
  if (maior > 4) return 0;
  if (menor < 0) return 0;
  if (p >= n) return (estado < 2);
  int &res = dp[p][maior][menor][estado];
  if (~res) return res;
  res = 0;
  // Place a P
  res = add (res, solve (p + 1, max (maior + 1, 3), menor + 1, calc (estado, 'P', w[p])));
  // Place a L
  res = add (res, solve (p + 1, maior - 1, min (menor - 1, 1) , calc (estado, 'L', w[p])));
  return res;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> MOD >> w;
  memset (dp, -1, sizeof(dp));
  cout << solve () << '\n';
  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