Submission #56173

#TimeUsernameProblemLanguageResultExecution timeMemory
56173aquablitz11Linear Garden (IOI08_linear_garden)C++14
85 / 100
1515 ms66560 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000010; const int INF = 1e9; int n, m; char str[N]; int dp[N][14]; bool vis[N][14]; inline int add(int a, int b) { return (a+b)%m; } inline int pos(int mn, int mx, int bal) { if (mn == 0) { if (mx == 0) return 0; if (mx == 1) return 1+bal; if (mx == 2) return 3+bal; } else if (mn == -1) { if (mx == 0) return 7+bal; if (mx == 1) return 9+bal; } else { return 13+bal; } } int solve1(int i, int mn, int mx, int bal) { if (mx-mn > 2) return 0; if (i == n) return 1; int j = pos(mn, mx, bal); if (vis[i][j]) return dp[i][j]; vis[i][j] = true; return dp[i][j] = add(solve1(i+1, min(mn, bal-1), mx, bal-1), solve1(i+1, mn, max(mx, bal+1), bal+1)); } int main() { scanf("%d%d %s", &n, &m, str); int mn = 0, mx = 0, bal = 0, ans = 1; for (int i = 0; i < n; ++i) { if (str[i] == 'P') { ans = add(ans, solve1(i+1, min(mn, bal-1), mx, bal-1)); ++bal; mx = max(mx, bal); } else { --bal; mn = min(mn, bal); } } printf("%d\n", ans); return 0; }

Compilation message (stderr)

linear_garden.cpp: In function 'int pos(int, int, int)':
linear_garden.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d %s", &n, &m, str);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...