oj.uz

답안 #376293

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
376293 2021-03-11T07:41:13 Z Nima_Naderi Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 1048576 KB 
///In the name of GOD
//#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 400 + 10;
int n, cnt[3][MXN];
int dp[3][MXN][MXN][MXN];
vector<int> Pos[3];
string s;
int Calc(int ch, int a, int b, int c){
    int now = 0, p = Pos[ch][(ch == 0 ? a : (ch == 1 ? b : c))];
    int ta = cnt[0][p - 1], tb = cnt[1][p - 1], tc = cnt[2][p - 1];
    now += max(0, ta - a);
    now += max(0, tb - b);
    now += max(0, tc - c);
    return now;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = "$" + s;
    memset(dp, 31, sizeof dp);
    for(int i = 1; i <= n; i ++){
        switch(s[i]){
            case 'R' : s[i] = 'A'; break;
            case 'G' : s[i] = 'B'; break;
            case 'Y' : s[i] = 'C'; break;
        }
        cnt[0][i] = cnt[0][i - 1];
        cnt[1][i] = cnt[1][i - 1];
        cnt[2][i] = cnt[2][i - 1];
        cnt[s[i] - 'A'][i] ++;
        Pos[s[i] - 'A'].push_back(i);
    }
    if(max({cnt[0][n], cnt[1][n], cnt[2][n]}) > (n + 1) / 2)
        return cout << -1, 0;
    dp[0][1][0][0] = Calc(0, 0, 0, 0);
    dp[1][0][1][0] = Calc(1, 0, 0, 0);
    dp[2][0][0][1] = Calc(2, 0, 0, 0);
    for(int a = 0; a <= cnt[0][n]; a ++){
        for(int b = 0; b <= cnt[1][n]; b ++){
            for(int c = 0; c <= cnt[2][n]; c ++){
                if(a + b + c == 0) continue;
                if(a < cnt[0][n]){
                    int* DP = &dp[0][a + 1][b][c];
                    (*DP) = min((*DP), dp[1][a][b][c] + Calc(0, a, b, c));
                    (*DP) = min((*DP), dp[2][a][b][c] + Calc(0, a, b, c));
                }
                if(b < cnt[1][n]){
                    int* DP = &dp[1][a][b + 1][c];
                    (*DP) = min((*DP), dp[0][a][b][c] + Calc(1, a, b, c));
                    (*DP) = min((*DP), dp[2][a][b][c] + Calc(1, a, b, c));
                }
                if(c < cnt[2][n]){
                    int* DP = &dp[2][a][b][c + 1];
                    (*DP) = min((*DP), dp[0][a][b][c] + Calc(2, a, b, c));
                    (*DP) = min((*DP), dp[1][a][b][c] + Calc(2, a, b, c));
                }
            }
        }
    }
    int ans = dp[0][cnt[0][n]][cnt[1][n]][cnt[2][n]];
    ans = min(ans, dp[1][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
    ans = min(ans, dp[2][cnt[0][n]][cnt[1][n]][cnt[2][n]]);
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1158 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1158 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1158 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1158 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -