oj.uz

Submission #72660

# Submission time Handle Problem Language Result Execution time Memory
72660 2018-08-26T13:43:03 Z Hoget157 Miners (IOI07_miners) C++14
100 / 100
 195 ms 1220 KB 
#include <bits/stdc++.h>
#define INF 1e+18
#define int long long
using namespace std;

int knd(int a,int b,int c){
	int cnt[4] = {};
	if(!cnt[a]) cnt[a]++;
	if(!cnt[b]) cnt[b]++;
	if(!cnt[c]) cnt[c]++;
	return cnt[1] + cnt[2] + cnt[3];
}

signed main(){
	int n,dp[2][4][4][4][4],now = 0,nxt = 1,ma = 0;
	string s;
	cin >> n >> s;
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 4;j++){
			for(int k = 0;k < 4;k++){
				for(int l = 0;l < 4;l++){
					dp[0][i][j][k][l] = -INF;
					dp[1][i][j][k][l] = -INF;
				}
			}
		}
	}
	dp[0][0][0][0][0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < 4;j++){
			for(int k = 0;k < 4;k++){
				for(int l = 0;l < 4;l++){
					for(int m = 0;m < 4;m++){
						int num,add = 0;
						if(s[i] == 'M') num = 1;
						else if(s[i] == 'B') num = 2;
						else num = 3;
						dp[nxt][k][num][l][m] = max(dp[nxt][k][num][l][m],dp[now][j][k][l][m] + knd(j,k,num));
						dp[nxt][j][k][m][num] = max(dp[nxt][j][k][m][num],dp[now][j][k][l][m] + knd(l,m,num));
					}
				}
			}
		}
		
		swap(now,nxt);
	}
	for(int i = 0;i < 4;i++){
		for(int j = 0;j < 4;j++){
			for(int k = 0;k < 4;k++){
				for(int l = 0;l < 4;l++) ma = max(ma,dp[now][i][j][k][l]);
			}
		}
	}
	cout << ma << endl;
	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:34:15: warning: unused variable 'add' [-Wunused-variable]
       int num,add = 0;
               ^~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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