Submission #94909

#	Time	Username	Problem	Language	Result	Execution time	Memory
94909		Retro3014	Miners (IOI07_miners)	C++17	100 / 100	92 ms	1144 KiB

miners

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;
#define MAX_N 100000
#define INF 1000000000
int N;
string str;
int arr[MAX_N+1];

int dp1[4][4][4][4], dp2[4][4][4][4];

int main(){
	scanf("%d", &N);
	cin>>str;
	for(int i=0; i<N; i++){
		if(str[i]=='M')	arr[i] = 1;
		else if(str[i]=='F')	arr[i] = 2;
		else	arr[i] = 3;
	}
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			for(int k=0; k<4; k++){
				for(int t=0; t<4; t++){
					dp1[i][j][k][t] = -INF;
				}
			}
		}
	}
	dp1[0][0][0][0] = 0;
	for(int T=0; T<N; T++){
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				for(int k=0; k<4; k++){
					for(int t=0; t<4; t++){
						dp2[i][j][k][t] = -INF;
					}
				}
			}
		}
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				for(int k=0; k<4; k++){
					for(int t=0; t<4; t++){
						if(dp1[i][j][k][t]==-INF)	continue;
						if(k==0){
							if(t==0){
								dp2[i][j][0][arr[T]] = max(dp2[i][j][0][arr[T]], dp1[i][j][k][t]+1);
							}
							else if(t==arr[T]){
								dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+1);
							}else{
								dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+2);
							}
						}else{
							int cnt = 0;
							cnt+=(k==t);
							cnt+=(k==arr[T]);
							cnt+=(t==arr[T]);
							if(cnt==0){
								dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+3);
							}else if(cnt==1){
								dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+2);
							}else{
								dp2[i][j][t][arr[T]] = max(dp2[i][j][t][arr[T]], dp1[i][j][k][t]+1);
							}
						}

						if(i==0){
							if(j==0){
								dp2[0][arr[T]][k][t] = max(dp2[0][arr[T]][k][t], dp1[i][j][k][t]+1);
							}else if(arr[T]==j){
								dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+1);
							}else{
								dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+2);
							}
						}else{
							int cnt = 0;
							cnt+=(i==j);
							cnt+=(i==arr[T]);
							cnt+=(j==arr[T]);
							if(cnt==0){
								dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+3);
							}else if(cnt==1){
								dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+2);
							}else{
								dp2[j][arr[T]][k][t] = max(dp2[j][arr[T]][k][t], dp1[i][j][k][t]+1);
							}
						}
					}
				}
			}
		}
		for(int i=0; i<4; i++){
			for(int j=0; j<4; j++){
				for(int k=0; k<4; k++){
					for(int t=0; t<4; t++){
						dp1[i][j][k][t] = dp2[i][j][k][t];
					}
				}
			}
		}
	}
	int ans = 0;
	for(int i=0; i<4; i++){
		for(int j=0; j<4; j++){
			for(int k=0; k<4; k++){
				for(int t=0; t<4; t++){
					ans = max(ans, dp1[i][j][k][t]);
				}
			}
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

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 / 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