제출 #890411

#제출 시각아이디문제언어결과실행 시간메모리
890411MatjazLinear Garden (IOI08_linear_garden)C++14
95 / 100
1545 ms59184 KiB
// // 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[1000001][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(); cin >> N >> M >> s; for (int i=0;i<15;i++) dp[N][i] = 1; for (int i=N-1;i>=0;i--){ for (int j=0;j<15;j++){ int res = 0; if (next_state(j, -1) != -1) res = (res + dp[i+1][next_state(j, -1)]) % M; if (next_state(j, 1) != -1) res = (res + dp[i+1][next_state(j, 1)]) % M; dp[i][j] = res; //cout << i << " " << j << " " << dp[i][j] << endl; } } 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 + dp[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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...