Submission #406640

#	Time	Username	Problem	Language	Result	Execution time	Memory
406640		rqi	Linear Garden (IOI08_linear_garden)	C++14	65 / 100	81 ms	65540 KiB

linear_garden

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

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

#define mp make_pair
#define f first
#define s second

#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

int MOD;

struct mi{
	ll v;
	mi(){
		v = 0;
	}
	mi(ll _v){
		v = _v % MOD;
	}
};

mi& operator+=(mi& a, mi& b){
	a.v+=b.v;
	if(a.v >= MOD) a.v-=MOD;
	return a;
}

mi operator+(mi a, mi b){
	a+=b;
	return a;
}

const int mx = 1000005;
map<pi, mi> dp[mx];

int N;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> MOD;

	map<pair<pi, int>, mi> cur;
	map<pair<pi, int>, mi> ncur;

	cur[mp(mp(0, 0), 0)] = mi(1);
	dp[0][mp(0, 0)] = mi(1);

	for(int i = 1; i <= N; i++){
		// cout << "i = " << i << "\n";
		ncur.clear();
		for(pair<pair<pi, int>, mi> z: cur){
			//pair<pair<pi, int>, mi> u = z;
			for(int j = -1; j <= 1; j+=2){
				auto u = z;
				int pos = u.f.s+j;
				ckmin(u.f.f.f, pos);
				ckmax(u.f.f.s, pos);
				if(u.f.f.s-u.f.f.f > 2) continue;
				ncur[mp(u.f.f, pos)]+=u.s;
			}
		}
		swap(cur, ncur);
		for(auto u: cur){
			dp[i][u.f.f]+=u.s;
		}
		// for(auto u: cur){
		// 	cout << u.f.f.f << " " << u.f.f.s << " " << u.f.s << " " << u.s.v << "\n";
		// }
	}

	string s;
	cin >> s;

	pi bound = mp(0, 0);
	int pos = 0;
	mi ans = mi(1);
	for(int i = 0; i < sz(s); i++){
		if(s[i] == 'P'){
			int c_pos = pos-1; //add L
			for(auto u: dp[sz(s)-1-i]){
				pi dp_bound = bound;
				ckmin(dp_bound.f, c_pos+u.f.f);
				ckmax(dp_bound.s, c_pos+u.f.s);
				if(dp_bound.s-dp_bound.f > 2) continue;
				ans+=u.s;
			}
		}

		if(s[i] == 'L'){
			pos--;
		}
		else{
			pos++;
		}
		ckmin(bound.f, pos);
		ckmax(bound.s, pos);
	}

	cout << ans.v << "\n";
}

• 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