제출 #1340248

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1340248		JungPS	Linear Garden (IOI08_linear_garden)	C++20	75 / 100	6 ms	9648 KiB

linear_garden

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n,m;
string str;
int dp[100007][4][4];

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    cin >> str;
    for(int i=n;i>=0;--i){
        for(int mn=0;mn<3;++mn){
            for(int mx=0;mx<3;++mx){
                if(i==n){
                    dp[i][mn][mx]=1;
                    continue;
                }
				dp[i][mn][mx]=dp[i+1][max(0LL,mn-1)][mx+1]+dp[i+1][mn+1][max(0LL,mx-1)];
                dp[i][mn][mx]%=m;
            }
        }
    }
    int ans=1,mx=0,mn=0;
	for(int i=0;i<n;++i){
		if(str[i]=='L'){
            ++mn;
            mx=max(0LL,mx-1);
			continue;
		}
        ans+=dp[i+1][mn+1][max(0LL,mx-1)];
        ans%=m;
        mn=max(0LL,mn-1);
		++mx;
	}
    cout << ans;
}

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