oj.uz

Submission #53978

# Submission time Handle Problem Language Result Execution time Memory
53978 2018-07-02T06:44:54 Z 윤교준(#1456) Linear Garden (IOI08_linear_garden) C++11
100 / 100
 501 ms 59408 KB 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#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() {
	/*
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	*/

	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 - 1; 0 <= i; 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;
				for (nj = 0; 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 <= 2) {
				int j; for (j = 0; 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);
	}
	Ans = (Ans + 1) % MOD;
	cout << Ans << endl;

	return 0;
}

Compilation message

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:26: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:28: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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 488 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 624 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #11
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 672 KB Output is correct
2 Correct 2 ms 672 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct
2 Correct 2 ms 672 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 4 ms 748 KB Output is correct
3 Correct 4 ms 876 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1828 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2044 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4220 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4860 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 18768 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 24160 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 30756 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 37244 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 59408 KB Output is correct
2 Correct 421 ms 59408 KB Output is correct
3 Correct 501 ms 59408 KB Output is correct