제출 #266871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
266871		youssefbou62	Linear Garden (IOI08_linear_garden)	C++14	65 / 100	255 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 ;

    int dp[MAXN][2][6][6][6];
    int N ;
    ll M ;
    string s;
    void add(int& x ,int 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][2][2][2] = 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 || nxt_pref==3 || nxt_pref==-3||x == -3 || y == 3 || y == -3 || x == 3 )continue ;

                                    if(choice < S[i])
                                        add(dp[i+1][1][2+nxt_pref][2+x][2+y],dp[i][0][pref+2][lpref+2][hpref+2]);
                                    if(choice == S[i])
                                        add(dp[i+1][0][2+nxt_pref][2+x][2+y],dp[i][0][pref+2][lpref+2][hpref+2]);
                                    add(dp[i+1][1][2+nxt_pref][2+x][2+y],dp[i][1][pref+2][lpref+2][hpref+2]);
                        }
                    //    if(dp[i][1][pref][lpref][hpref])
                     //   cout << i << " " << pref << " " <<lpref << " " <<hpref<<endl;
                    }
        }

        int 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+2][lpref+2][hpref+2]);
        cout << ans << endl;
    }
    int main(){
      //  ifstream cin("in.in");
        cin >> N >> M >> s ;
        solve() ;
    }

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 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