Submission #480426

#	Time	Username	Problem	Language	Result	Execution time	Memory
480426		antontsiorvas	Miners (IOI07_miners)	C++14	100 / 100	167 ms	125624 KiB

miners

#include <bits/stdc++.h>
using namespace std;

int n, emf[4];
char food[100005];
int dp[100005][4][4][4][4]; // 0 for none, 1 for meat, 2 for fish, 3 for bread
bool vis[100005][4][4][4][4];

int retcode(char f){
	if(f == 'M') return 1;
	if(f == 'F') return 2;
	return 3;
}

int retcoal(int a, int b, int c){
	for(int i=1; i<4; i++) emf[i] = 0;
	emf[a]++, emf[b]++, emf[c]++;
	int ret = 0;
	for(int i=1; i<4; i++) if(emf[i]) ret++;
	return ret;
}

int main(){
	scanf("%d %s",&n,food+1);
	vis[1][0][0][0][0] = true;
	for(int i=1; i<=n; i++){
		for(int a1=0; a1<4; a1++){
			for(int a2=0; a2<4; a2++){
				for(int b1=0; b1<4; b1++){
					for(int b2=0; b2<4; b2++){
						if(!vis[i][a1][a2][b1][b2]) continue;
						int nf = retcode(food[i]);
						vis[i+1][nf][a1][b1][b2] = true;
						vis[i+1][a1][a2][nf][b1] = true; 
						dp[i+1][nf][a1][b1][b2] = max(dp[i+1][nf][a1][b1][b2], dp[i][a1][a2][b1][b2] + retcoal(a1,a2,nf));
						dp[i+1][a1][a2][nf][b1] = max(dp[i+1][a1][a2][nf][b1], dp[i][a1][a2][b1][b2] + retcoal(b1,b2,nf));
					}
				}
			}
		}
	}
	int ans = 0;
	for(int a1=0; a1<4; a1++){
		for(int a2=0; a2<4; a2++){
			for(int b1=0; b1<4; b1++){
				for(int b2=0; b2<4; b2++){
					ans = max(ans, dp[n+1][a1][a2][b1][b2]);
				}
			}
		}
	}
	printf("%d",ans);
}

Compilation message (stderr)

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

• 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