Submission #157090

#	Time	Username	Problem	Language	Result	Execution time	Memory
157090		youngyojun	Linear Garden (IOI08_linear_garden)	C++11	100 / 100	433 ms	60040 KiB

linear_garden

#include <bits/stdc++.h>
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
using namespace std;
typedef long long ll;
const int CS[] = { 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 1, 1, 1 };
const int CE[] = { 2, 3, 3, 4, 4, 4, 2, 2, 2, 2, 2, 3, 3, 3 };
const int CX[] = { 2, 2, 3, 2, 3, 4, 1, 2, 0, 1, 2, 1, 2, 3 };
 
const int MAXN = 1000002;
 
int dp[MAXN][14];
int A[MAXN];
 
int N, MOD, Ans;
 
int main() {
	scanf("%d%d", &N, &MOD);
	for(int i = 1; i <= N; i++) {
		char c; scanf(" %c", &c);
		A[i] = (c == 'P' ? 1 : -1);
	}
 
	for(int i = 0; i < 14; i++) dp[N][i] = 1;
	for(int i = N; i--;) {
		for(int j = 0; j < 14; j++) {
			int &ret = dp[i][j];
			int s = CS[j], e = CE[j], x = CX[j];
			for(int nx : {x-1, x+1}) {
				int ns = min(s, nx), ne = max(e, nx);
				if(ne-ns > 2) continue;
				int nj = 0; for(; CS[nj] != ns || CE[nj] != ne || CX[nj] != nx; nj++);
				ret = (ret + dp[i+1][nj]) % MOD;
			}
		}
	}
 
	for(int i = 1, s = 2, e = 2, x = 2; i <= N; i++) {
		if(A[i] < 0) {
			x--;
			upmin(s, x);
			upmax(e, x);
			continue;
		}
		{
			int xx = x-1, ss = min(s, xx), ee = max(e, xx);
			if(ee-ss < 3) {
				int j = 0; for(; j < 14 && (ss != CS[j] || ee != CE[j] || xx != CX[j]); j++);
				if(j < 14) Ans = (Ans + dp[i][j]) % MOD;
			}
		}
		x++;
		upmin(s, x);
		upmax(e, x);
	}
	cout << (Ans+1) % MOD << endl;
	return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:18: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:20:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c", &c);
           ~~~~~^~~~~~~~~~~

• 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