제출 #719951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719951		a_aguilo	Miners (IOI07_miners)	C++14	100 / 100	984 ms	443152 KiB

miners

#include<bits/stdc++.h>

using namespace std;

int N;
vector<int> food;
vector<vector<vector<vector<vector<int>>>>> DP;
//DP[leftBoats][Mine1Ship][Mine1Ship2][Mine2Ship][Mine2Ship2]

int solve(int boatsTillNow, int Mine1Ship, int Mine1Ship2, int Mine2Ship, int Mine2Ship2){
	//cout << boatsTillNow <<'\t' << Mine1Ship << '\t' << Mine1Ship2 << '\t' << Mine2Ship << '\t' << Mine2Ship2 << endl;
	if(boatsTillNow == N) return 0;
	if(DP[boatsTillNow][Mine1Ship][Mine1Ship2][Mine2Ship][Mine2Ship2] != -1) return DP[boatsTillNow][Mine1Ship][Mine1Ship2][Mine2Ship][Mine2Ship2];
	DP[boatsTillNow][Mine1Ship][Mine1Ship2][Mine2Ship][Mine2Ship2] = 0;
	int foodAct = food[boatsTillNow];
	int coal1, coal2;
	//Ship va a la mina 1
	if(Mine1Ship == 3){
		if(Mine1Ship2 == 3) coal1 = 1;
		else{
			if(foodAct == Mine1Ship2) coal1 = 1;
			else coal1 = 2;
		}
	}else{
		if(Mine1Ship == Mine1Ship2){
			if(foodAct == Mine1Ship) coal1 = 1;
			else coal1 = 2;
		}else{
			if(foodAct== Mine1Ship2 or foodAct == Mine1Ship) coal1 = 2;
			else coal1 = 3;
		}
	}
	coal1 += solve(boatsTillNow+1, Mine1Ship2, foodAct, Mine2Ship, Mine2Ship2);
	//Ship va a la mina 2
	if(Mine2Ship == 3){
		if(Mine2Ship2 == 3) coal2 = 1;
		else{
			if(foodAct == Mine2Ship2) coal2 = 1;
			else coal2 = 2;
		}
	}else{
		if(Mine2Ship2==Mine2Ship){
			if(foodAct == Mine2Ship2) coal2 = 1;
			else coal2 = 2;
		}else{
			if(foodAct==Mine2Ship or foodAct==Mine2Ship2) coal2 = 2;
			else coal2 = 3;
		}
	}
	coal2 += solve(boatsTillNow+1, Mine1Ship, Mine1Ship2, Mine2Ship2, foodAct);
	//if(coal2 < coal1) cout << boatsTillNow << " " << 1 << endl;
	//else cout << boatsTillNow << " " << 2 << endl;
	return DP[boatsTillNow][Mine1Ship][Mine1Ship2][Mine2Ship][Mine2Ship2] = max(coal1, coal2);
}


int main(){
	cin >> N;
	DP = vector<vector<vector<vector<vector<int>>>>>(N, vector<vector<vector<vector<int>>>>(4, vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));
	char c;
	food = vector<int>(N);
	for(int i = 0; i < N; ++i){
		cin >> c;
		if(c == 'F') food[i] = 0;
		else if(c == 'M') food[i] = 1;
		else food[i] = 2;
	}
	cout<<solve(0, 3, 3, 3, 3) << endl;
	return 0;
}

• 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