Submission #165335

#	Time	Username	Problem	Language	Result	Execution time	Memory
165335		Akashi	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	357 ms	254840 KiB

joi2019_ho_t3

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

int n;
int f[4];
int a[401];
char s[401];
int pos[4][401];
int ad[401][4];
long long dp[201][201][201][4];

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);
    scanf("%s", s + 1);

    for(int i = 1; i <= n ; ++i){
        if(s[i] == 'R') a[i] = 1;
        if(s[i] == 'Y') a[i] = 2;
        if(s[i] == 'G') a[i] = 3;
        ++f[a[i]];
        pos[a[i]][f[a[i]]] = i;
    }

    if(f[1] > n / 2 + n % 2 || f[2] > n / 2 + n % 2 || f[3] > n / 2 + n % 2){
        printf("-1");
        return 0;
    }

    for(int i = 1; i <= 3 ; ++i){
        int NR = 0;
        for(int p = 1; p <= n ; ++p){
            if(a[p] == i) ++NR;
            ad[p][i] = NR;
        }
    }

    memset(dp, 0x3f3f3f3f, sizeof(dp));

    if(f[1] > 0) dp[1][0][0][1] = pos[1][1] - 1;
    if(f[2] > 0) dp[0][1][0][2] = pos[2][1] - 1;
    if(f[3] > 0) dp[0][0][1][3] = pos[3][1] - 1;

    int a, b, c, a2, b2, c2, l1, l2;
    for(int i = 2; i <= n ; ++i){
        for(a = 0; a <= i && a <= f[1] ; ++a){
            for(b = 0; b <= i - a && b <= f[2] ; ++b){
                c = i - a - b;
                if(c > f[3]) continue ;

                for(int last = 1; last <= 3 ; ++last){
                    a2 = a, b2 = b, c2 = c;
                    if(last == 1) --a2, l1 = 2, l2 = 3;
                    if(last == 2) --b2, l1 = 1, l2 = 3;
                    if(last == 3) --c2, l1 = 1, l2 = 2;

                    if(a2 < 0 || b2 < 0 || c2 < 0) continue ;

                    if(last == 1){
                        int act_pos = pos[1][a] + max(0, b - ad[pos[1][a]][2]) + max(0, c - ad[pos[1][a]][3]);
                        dp[a][b][c][last] = min(dp[a][b][c][last], min(dp[a2][b2][c2][l1], dp[a2][b2][c2][l2]) + abs(act_pos - i));
                    }
                    else if(last == 2){
                        int act_pos = pos[2][b] + max(0, a - ad[pos[2][b]][1]) + max(0, c - ad[pos[2][b]][3]);
                        dp[a][b][c][last] = min(dp[a][b][c][last], min(dp[a2][b2][c2][l1], dp[a2][b2][c2][l2]) + abs(act_pos - i));
                    }
                    else if(last == 3){
                        int act_pos = pos[3][c] + max(0, a - ad[pos[3][c]][1]) + max(0, b - ad[pos[3][c]][2]);
                        dp[a][b][c][last] = min(dp[a][b][c][last], min(dp[a2][b2][c2][l1], dp[a2][b2][c2][l2]) + abs(act_pos - i));
                    }
                }
            }
        }
    }

    long long Sol = dp[f[1]][f[2]][f[3]][1];
    for(int i = 2; i <= n ; ++i) Sol = min(Sol, dp[f[1]][f[2]][f[3]][i]);

    printf("%lld", Sol);

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25