Submission #118696

#	Time	Username	Problem	Language	Result	Execution time	Memory
118696		eriksuenderhauf	Linear Garden (IOI08_linear_garden)	C++11	100 / 100	297 ms	10204 KiB

linear_garden

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 5;
const double eps = 1e-9;
char str[MAXN];
int mx[MAXN], mi[MAXN], dp[2][5][5][5];

int main() {
	int n;
	scanf("%d %d", &n, &MOD);
	scanf("%s", str);
	int cur = 0, a = 0, b = 0;
	for (int i = 0; i < n; i++) {
		cur--;
		mx[i] = max(a - cur, 0);
		mi[i] = min(b - cur, 0);
		if (str[i] == 'P')
			cur += 2;
		a = max(a, cur);
		b = min(b, cur);
	}
	int ans = 1;
	dp[0][2][2][2] = 1;
	for (int i = n - 1; i >= 0; i--) {
		if (str[i] == 'P') {
			for (int j = 0; j <= 2; j++)
				for (int k = 2; k <= j + 2; k++)
					for (int l = j; l <= k; l++)
						if (max(k, l + mx[i]) - min(j, l + mi[i]) <= 2)
							ans = (ans + dp[0][j][k][l]) % MOD;
		}
		for (int j = 0; j <= 2; j++)
			for (int k = 2; k <= j + 2; k++)
				for (int l = j; l <= min(3, k); l++)
					dp[1][j][max(k, l + 1)][l + 1] = (dp[1][j][max(k, l + 1)][l + 1] + dp[0][j][k][l]) % MOD;
		for (int j = 0; j <= 2; j++)
			for (int k = 2; k <= j + 2; k++)
				for (int l = max(1, j); l <= k; l++)
					dp[1][min(j, l - 1)][k][l - 1] = (dp[1][min(j, l - 1)][k][l - 1] + dp[0][j][k][l]) % MOD;
		swap(dp[0], dp[1]);
		mem(dp[1], 0);
	}
	pri(ans);
    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &MOD);
  ~~~~~^~~~~~~~~~~~~~~~~~~
linear_garden.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str);
  ~~~~~^~~~~~~~~~~

• 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