oj.uz

Submission #480426

# Submission time Handle Problem Language Result Execution time Memory
480426 2021-10-16T07:44:17 Z antontsiorvas Miners (IOI07_miners) C++14
100 / 100
 167 ms 125624 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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