# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
480426 | 2021-10-16T07:44:17 Z | antontsiorvas | Miners (IOI07_miners) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1484 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 6524 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 12740 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 51 ms | 31556 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 94276 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 167 ms | 125624 KB | Output is correct |