Submission #266837

#	Time	Username	Problem	Language	Result	Execution time	Memory
266837		youssefbou62	Linear Garden (IOI08_linear_garden)	C++14	0 / 100	58 ms	65540 KiB

linear_garden

#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 = 1e6+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() ;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 2
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 4
• Subtask 7: 0 / 4
• Subtask 8: 0 / 4
• Subtask 9: 0 / 4
• Subtask 10: 0 / 4
• Subtask 11: 0 / 4
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5
• Subtask 22: 0 / 5
• Subtask 23: 0 / 5