oj.uz

Submission #227383

# Submission time Handle Problem Language Result Execution time Memory
227383 2020-04-27T09:15:27 Z anubhavdhar Miners (IOI07_miners) C++14
100 / 100
 185 ms 888 KB 
#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 = 1e5+5;
const ll ROOTN = 320;

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

int N;
int dpNow[4][4][4][4], dpPrev[4][4][4][4], A[MAXN];

#define to_int(c) ((c=='B') ? 1 : ((c=='F') ? 2 : 3))

inline int work_done(int a,int b,int c)
{
	if(b == 0)	b = a;
	if(c == 0)	c = a;
	return ((a == b and a == c) ? 1 : ((a == b or b == c or c == a) ? 2 : 3) );
}

int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	
	int i,a,b,c,d;
	char ch;

	// while(true)
	// {
	// 	cin>>a>>b>>c;
	// 	cout<<work_done(a,b,c)<<endl;
	// }

	cin>>N;
	int ans = N;
	FOR(i,N)
	{
		cin>>ch;
		A[i] = to_int(ch);
	}

	FOR(a,4)
		FOR(b,4)
			FOR(c,4)
				FOR(d,4)
					dpPrev[a][b][c][d] = -1e9;
	dpPrev[0][0][0][0] = 0;
	FOR(i,N)
	{
		FOR(a,4)
			FOR(b,4)
				FOR(c,4)
					FOR(d,4)
						dpNow[a][b][c][d] = -1e9;

		FOR(a,4)
			FOR(b,4)
				FOR(c,4)
					FOR(d,4)
					{
						dpNow[A[i]][a][b][c] = max((dpPrev[a][d][b][c] + work_done(A[i],a,d)),dpNow[A[i]][a][b][c]);
						dpNow[a][b][A[i]][c] = max((dpPrev[a][b][c][d] + work_done(A[i],c,d)),dpNow[a][b][A[i]][c]);
					}

				
		FOR(a,4)
			FOR(b,4)
				FOR(c,4)
					FOR(d,4)
						dpPrev[a][b][c][d] = dpNow[a][b][c][d];

		// FOR(a,4)
		// 	FOR(b,4)
		// 		FOR(c,4)
		// 			FOR(d,4)
		// 				if(dpNow[a][b][c][d] >= 0)
		// 					printf("dp[%d][%d][%d][%d][%d] = %d\n",i,a,b,c,d,dpNow[a][b][c][d]);
	}
	FOR(a,4)
		FOR(b,4)
			FOR(c,4)
				FOR(d,4)
					ans = max(dpNow[a][b][c][d],ans);
	cout<<ans;
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 384 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 384 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 512 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 888 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 756 KB Output is correct