oj.uz

Submission #167402

# Submission time Handle Problem Language Result Execution time Memory
167402 2019-12-08T08:24:53 Z Nightlight Miners (IOI07_miners) C++14
100 / 100
 356 ms 1016 KB 
#include<bits/stdc++.h>
using namespace std;
int n; string s;
vector<int>v;
int dp[2][4][4][4][4];
int cnt(int m, int b, int f){
	int rsm, rsb, rsf;
	if(m==3) rsm=0; else rsm=1<<m;
	if(b==3) rsb=0; else rsb=1<<b;
	if(f==3) rsf=0; else rsf=1<<f;
	int rs=rsm|rsb|rsf;
	int cnt=__builtin_popcount(rs);
	return cnt;
}
int main(){
	scanf("%d", &n);
	cin>>s; v.resize(n);
	for(int i=0; i<n; i++){
		if(s[i]=='M') v[i]=0;
		else if(s[i]=='B') v[i]=1;
		else v[i]=2;
	}
	for(int i=n-1; i>=0; 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++){
						dp[i%2][j][k][l][m]=max(dp[(i+1)%2][k][v[i]][l][m]+cnt(j, k, v[i]),
												dp[(i+1)%2][j][k][m][v[i]]+cnt(l, m, v[i]));
					}
				}
			}
		}
	}
	printf("%d\n", dp[0][3][3][3][3]);
	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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