oj.uz

Submission #109245

# Submission time Handle Problem Language Result Execution time Memory
109245 2019-05-05T19:12:45 Z amiratou Miners (IOI07_miners) C++14
100 / 100
 286 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int change(char car){
	if(car=='F')return 1;
	if(car=='M')return 2;
	return 3;
}
int score( int a, int b, int c ){
	int ret = 0;
	for( int i = 1; i <= 3 ; i++ )
		if( a == i || b == i || c == i )
			ret++;
	return ret;
}
int tab[100005],dp[2][4][4][4][4];
int main(){
	boost;
	int n;
	char car;
	cin>>n;
	for (int i = 0; i < n; ++i)
	{
		cin>>car;
		tab[i]=change(car);
	}
	for (int i = n-1; i >= 0; --i)
	{
		for (int a = 0; a < 4; ++a)
		{
			for (int b = 0; b < 4; ++b){
				for (int c = 0; c < 4; ++c){
					for (int d = 0; d < 4; ++d){
						dp[i%2][a][b][c][d]=max(dp[(i+1)%2][tab[i]][a][c][d]+score(tab[i],a,b),
							score(c,d,tab[i])+dp[(i+1)%2][a][b][tab[i]][c]);
					}
				}
			}
		}
	}
	cout<<dp[0][0][0][0][0];
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 724 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 768 KB Output is correct