Submission #56176

#TimeUsernameProblemLanguageResultExecution timeMemory
56176aquablitz11Linear Garden (IOI08_linear_garden)C++14
100 / 100
292 ms62464 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][15]; 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 if (mn == -2) { if (mx == 0) return 13+bal; } return 14; } int main() { scanf("%d%d %s", &n, &m, str); for (int i = n; i >= 0; --i) { for (int mn = -2; mn <= 0; ++mn) { for (int mx = max(mn, 0); mx-mn <= 2; ++mx) { for (int bal = mn; bal <= mx; ++bal) { int j = pos(mn, mx, bal); if (i == n) dp[i][j] = 1; else dp[i][j] = add(dp[i+1][pos(min(mn, bal-1), mx, bal-1)], dp[i+1][pos(mn, max(mx, bal+1), bal+1)]); } } } } int mn = 0, mx = 0, bal = 0, ans = 1; for (int i = 0; i < n; ++i) { if (str[i] == 'P') { ans = add(ans, dp[i+1][pos(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 main()':
linear_garden.cpp:29: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...