Submission #227138

#	Time	Username	Problem	Language	Result	Execution time	Memory
227138		anubhavdhar	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	94 ms	55420 KiB

linear_garden

#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

//const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 1e6+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

ll N,MOD,dp[MAXN][3];
vector<bool> V;

ll DP(ll ind,short int sum,short int min_sum,short int max_sum)
{
	// cout<<"In DP("<<ind<<','<<sum<<','<<min_sum<<','<<max_sum<<")\n";
	assert(abs(sum) <= 2);
	if(abs(sum) == 2 or abs(min_sum) == 2 or abs(max_sum) == 2)
		return ((ind == N-1) ? 0 : DP(ind + 1,sum + (V[ind]?1:-1),min(0,min_sum + (V[ind]?1:-1)),max(0,max_sum + (V[ind]?1:-1))));
	if(ind == N-1)
	{
		// cout<<"DP("<<ind<<") = "<<((V[ind])?1:0)<<endl;
		return ((V[ind])?1:0);
	}
	sum += V[ind]?1:-1;
	min_sum += V[ind]?1:-1;
	max_sum += V[ind]?1:-1;
	ll val = DP(ind + 1,sum,min((short int)0,min_sum),max((short int)0,max_sum));
	short int p = max(max(abs(min_sum-2),abs(max_sum-2)),abs(sum-2));
	// cout<<"DP("<<ind<<") = "<<((V[ind])?1:0)*(dp[N-1-ind][p]) + val<<" where p = "<<p<<endl;
	return (((V[ind])?(dp[N-1-ind][p]):0) + val)%MOD;
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>N>>MOD;
	char c;
	int i;
	dp[1][0] = 2;dp[1][1] = 2;dp[1][2] = 1;
	dp[2][0] = 4;dp[2][1] = 3;dp[2][2] = 2;
	dp[3][0] = 6;dp[3][1] = 5;dp[3][2] = 2;
	ll pow = 2,pow1 = 2;
	FOR(i,N+1)
	{
		if(i > 2 and i%2 == 1) pow = (pow*2)%MOD;
		if(i > 3 and i%2 == 1) pow1 = (pow1*2)%MOD;
		if(i > 2) dp[i+1][0] = (dp[i][0] + pow)%MOD;
		if(i > 3) 
		{
			dp[i][1] = (dp[i-1][1] + pow1)%MOD;
			dp[i][2] = (dp[i-1][2]*(((i%2) == 0)?2:1))%MOD;
		}
	}
	// FORe(i,N)
		// cout<<dp[i][0]<<' '<<dp[i][1]<<' '<<dp[i][2]<<endl;
	FOR(i,N)
	{
		cin>>c;
		V.pb((c == 'P'));
	}
	cout<<(DP(0,0,0,0)+1)%MOD;
	return 0;
}

• 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