oj.uz

Submission #719951

# Submission time Handle Problem Language Result Execution time Memory
719951 2023-04-07T07:00:16 Z a_aguilo Miners (IOI07_miners) C++14
100 / 100
 984 ms 443152 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 22396 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 44444 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 110924 KB Output is correct

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 984 ms 443152 KB Output is correct