제출 #266846

#제출 시각아이디문제언어결과실행 시간메모리
266846youssefbou62Linear Garden (IOI08_linear_garden)C++14
50 / 100
96 ms28124 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") using namespace std; #define mp make_pair #define fi first #define se second #define all(v) v.begin(),v.end() #define allarr(a) a , a + n #define ll long long #define pb push_back #define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL) #define sz(x) (int)x.size() typedef pair<int, int> pi; typedef pair<ll,ll> pll ; typedef pair<int,pi> trp ; typedef vector<pi> vpi; typedef priority_queue< pi, vector <pi> , greater<pi> > spq; const int MAXN = 400+5 ; map<int,map<int,map<int,ll>>> dp[MAXN][2]; int N ; ll M ; string s; void add(ll& x , ll y ){ x = ( x % M + y % M ) % M ; } void solve (){ vector<int> S ; for(int i = 0 ; i < N ; i++ )S.pb(s[i]=='P'); dp[0][0][0][0][0] = 1 ; for(int i = 0 ; i < N ; i++ ){ for(int pref = -2 ; pref <= 2 ; pref++ ) for(int hpref = -2 ; hpref <= 2 ; hpref++ ) for(int lpref = -2 ; lpref <= 2 ; lpref++ ){ for(int choice : {0,1}){ int nxt_pref = pref ; if( choice )nxt_pref++;else nxt_pref--; int x = min(nxt_pref,lpref) ; int y = max(nxt_pref,hpref); if( abs(hpref-lpref) > 2 )continue ; if(choice < S[i]) add(dp[i+1][1][nxt_pref][x][y],dp[i][0][pref][lpref][hpref]); if(choice == S[i]) add(dp[i+1][0][nxt_pref][x][y],dp[i][0][pref][lpref][hpref]); add(dp[i+1][1][nxt_pref][x][y],dp[i][1][pref][lpref][hpref]); } // if(dp[i][1][pref][lpref][hpref]) // cout << i << " " << pref << " " <<lpref << " " <<hpref<<endl; } } ll ans = 1 ; for(int pref = -2 ; pref <= 2 ; pref++ ) for(int hpref = -2 ; hpref <= 2 ; hpref++ ) for(int lpref = -2 ; lpref <= 2 ; lpref++) if( abs(hpref-lpref) <= 2 ) add(ans,dp[N][1][pref][lpref][hpref]); cout << ans << endl; } int main(){ // ifstream cin("in.in"); cin >> N >> M >> s ; solve() ; }
#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...