//
// IOI2008Garden.cpp
//
//
// Created by Matjaz Leonardis on 17/12/2023.
//
#include <iostream>
#include <string>
#include <string.h>
#include <map>
using namespace std;
int N,M;
string s;
int dp[1000000][15];
map<pair<pair<int,int>, int>, int > vtos;
map<int,pair<pair<int,int>, int> > stov;
int next_state(int state, int incrament){
pair<pair<int,int>,int> st = stov[state];
int max_point = st.first.first;
int interval_length = st.first.second;
int running_total = st.second;
//cout << "(" << max_point << "," << interval_length << "," << running_total << ") + " << incrament;
running_total += -incrament;
if (running_total > interval_length || running_total < 0){
interval_length++;
if (running_total < 0) {
max_point++;
running_total = 0;
}
}
//cout << " -> (" << max_point << "," << interval_length << "," << running_total << ")" << endl;
pair<pair<int,int>,int> new_st = make_pair(make_pair(max_point, interval_length), running_total);
if (vtos.count(new_st) == 0) return -1; else return vtos[new_st];
}
int count(int x, int state){
if (x == N) return 1;
if (dp[x][state] != -1) return dp[x][state];
int res = 0;
if (next_state(state, -1) != -1) res = (res + count(x+1,next_state(state, -1))) % M;
if (next_state(state, 1) != -1) res = (res + count(x+1,next_state(state, 1))) % M;
return dp[x][state] = res;
}
void make_state_dictionaries(){
int state_count = 0;
for (int interval_length = 0;interval_length <= 2; interval_length++){
for (int max_point=0;max_point<=interval_length;max_point++){
for (int running_total=0;running_total<=interval_length;running_total++){
pair<pair<int,int>, int> st = make_pair(make_pair(max_point, interval_length), running_total);
stov[state_count] = st;
vtos[st] = state_count;
state_count++;
}
}
}
}
int main(){
make_state_dictionaries();
memset(dp, -1, sizeof(dp));
cin >> N >> M >> s;
int res = 0;
int current_state = 0;
for (int i=0;i<N;i++){
if (s[i] =='P' && next_state(current_state, -1) != -1) res = (res + count(i + 1, next_state(current_state, -1) ) ) % M;
//cout << res << " " << next_state(current_state, -1) << endl;
current_state = next_state(current_state, s[i] == 'P' ? 1 : -1);
}
cout << (res + 1) % M << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
58968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58968 KB |
Output is correct |
2 |
Correct |
7 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
58972 KB |
Output is correct |
2 |
Correct |
8 ms |
58972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
59228 KB |
Output is correct |
2 |
Correct |
10 ms |
59228 KB |
Output is correct |
3 |
Correct |
7 ms |
59084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
60248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
60440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
63068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
63832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
29 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
25 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
30 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
38 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |