제출 #109245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109245		amiratou	Miners (IOI07_miners)	C++14	100 / 100	286 ms	768 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8