Submission #1338521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338521		hyyh	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	45 ms	2300 KiB

linear_garden

#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
#define endl '\n'
#define f first
#define s second
#define all(x) begin(x),end(x)

int dp[2][3][3];//subdiff of L,P

int main(){
    int n;cin >> n;
    int m;cin >> m;
    string st;cin >> st;
    int N = st.size();
    int valL = 0;
    int valP = 0;
    for(int i{};i < N;i++){
        if(st[i] == 'P'){
            if(valL < 2) dp[i%2][valL+1][max(0,valP-1)] = (dp[i%2][valL+1][max(0,valP-1)]+1)%m;
            valP++;
            valL = max(0,valL-1);
        }
        else{
            valL++;
            valP = max(0,valP-1);
        }
        for(int j{};j < 3;j++){
            for(int k{};k < 3;k++){
                if(k < 2) dp[(i+1)%2][max(0,j-1)][k+1] = (dp[(i+1)%2][max(0,j-1)][k+1]+dp[i%2][j][k])%m;
                if(j < 2) dp[(i+1)%2][j+1][max(0,k-1)] = (dp[i%2][j][k]+dp[(i+1)%2][j+1][max(0,k-1)])%m;
                if(i != N-1) dp[i%2][j][k] = 0;
            }
        }
    }
    N--;
    int sum = 1;
    for(int i{};i < 3;i++){
        for(int j{};j < 3;j++){
            sum = (sum+dp[N%2][i][j])%m;
        }
    }
    cout << sum;
}

• 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: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5