oj.uz

Submission #777873

# Submission time Handle Problem Language Result Execution time Memory
777873 2023-07-09T19:56:24 Z raysh07 Linear Garden (IOI08_linear_garden) C++17
100 / 100
 70 ms 3312 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, mod;
string str;

int dp[2][3][3][2];
void add(int &x, int val){
	x += val;
	if(x >= mod)
		x-= mod;
}

int32_t main(){
	cin >> n >> mod >> str;

	dp[0][0][0][1] = 1;
	for(int i = 0; i < n; i++){
		char c = str[i];
		for(int mi = 0; mi <= 2; mi++){
			for(int ma = 0; ma <= 2; ma++){
			 if(ma != 2) {
                if(c == 'L') {
                    add(dp[(i+1)%2][max(0LL, mi- 1)][ma + 1][1], dp[i%2][mi][ma][1]);
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                } else {
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][0]);
                    add(dp[(i+1)%2][max(0LL, mi - 1)][ma + 1][0], dp[i%2][mi][ma][1]);
                }
            }
            if(mi != 2) {
                if(c == 'P') {
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][1], dp[i%2][mi][ma][1]);
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][0], dp[i%2][mi][ma][0]);
                } else {
                    add(dp[(i+1)%2][mi + 1][max(0LL, ma - 1)][0], dp[i%2][mi][ma][0]);
                }
            }
            dp[i%2][mi][ma][0] = dp[i%2][mi][ma][1] = 0;
			}
		}
	}

	int sum = 0;
	for(int mi = 0; mi <= 2; mi++){
		for(int ma = 0; ma <= 2; ma++){
			add(sum, dp[n%2][mi][ma][0]);
			add(sum, dp[n%2][mi][ma][1]);
		}
	}

	cout << sum << "\n";
	return 0;
}

Subtask #1
2.0 / 2.0

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

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
4.0 / 4.0

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

Subtask #7
4.0 / 4.0

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

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #11
4.0 / 4.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

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

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

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

Subtask #17
5.0 / 5.0

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

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 440 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1252 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1296 KB Output is correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1904 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2076 KB Output is correct

Subtask #23
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3256 KB Output is correct
2 Correct 51 ms 3236 KB Output is correct
3 Correct 70 ms 3312 KB Output is correct