Submission #838811

#	Time	Username	Problem	Language	Result	Execution time	Memory
838811		teo_thrash	Linear Garden (IOI08_linear_garden)	C++14	10 / 100	123 ms	48360 KiB

linear_garden

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn=1e6+3;
const int mod=1e9+7;

int n, m;
string a;

ll dp[maxn][6];

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

cin>>n>>m;
cin>>a;

int sz=a.size();

if(sz%2==0){

    dp[sz][1]=1;
    dp[sz][2]=0;
    dp[sz][3]=1;
    dp[sz][4]=0;
    dp[sz][5]=1;

}else{
    
    dp[sz][1]=0;
    dp[sz][2]=1;
    dp[sz][3]=0;
    dp[sz][4]=1;
    dp[sz][5]=0;

}

for(int i=sz-1; i>=0; i--){
    for(int j=1; j<=5; j++){
        if(i%2==0){
            dp[i][1]=dp[i+1][2]%m;
            dp[i][5]=dp[i+1][4]%m;


            if(i+3<=sz){
                dp[i][1]-=dp[i+3][4];
                dp[i][1]%=m;

                dp[i][5]-=dp[i+3][2];
                dp[i][5]%=m;
            }

            dp[i][3]=(dp[i+1][2]+dp[i+1][4])%m;

        }else{

            dp[i][2]=(dp[i+1][1]+dp[i+1][3])%m;
            dp[i][4]=(dp[i+1][3]+dp[i+1][5])%m;

            
            if(i+3<=sz){
                dp[i][2]-=dp[i+3][5];
                dp[i][2]%=m;

                dp[i][4]-=dp[i+3][1];
                dp[i][4]%=m;
            }

        }
    }
}
/*
for(int i=0; i<=sz; i++){
    for(int j=1; j<=5; j++){
        cout<<dp[i][j]<<" ";
    }
    cout<<endl;
}*/

ll ans=0, bal=0;

for(int i=0; i<a.size(); i++){
    
    if(a[i]=='P'){
        bal--;

        if(bal<1){
            ans+=dp[i+1][bal+5];
            ans%=m;
        }
    }else{
        bal++;
    }
}
//int add=!(n%2);
cout<<(ans+1)%m;
return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 | for(int i=0; i<a.size(); i++){
      |              ~^~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 2
• Subtask 3: 4 / 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: 4 / 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