Submission #743426

#	Time	Username	Problem	Language	Result	Execution time	Memory
743426		mickey080929	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	185 ms	389700 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 1e9;

int n;
int a[410];
int cnt[410];
int inv[3][410][3];
int dp[410][410][410][3];

int main() {
    int i, j, k, r, g, y;
    scanf("%d", &n);
    for (i=1; i<=n; i++) {
        char c;
        scanf(" %c", &c);
        if (c == 'G') a[i] = 1;
        else if (c == 'Y') a[i] = 2;
    }
    for (i=1; i<=n; i++) {
        cnt[a[i]] ++;
        for (j=0; j<3; j++) {
            if (j == a[i]) continue;
            inv[a[i]][cnt[a[i]]][j] = cnt[j];
        }
    }
    int R = cnt[0], G = cnt[1], Y = cnt[2];
    if (max({R, G, Y}) > (n+1)/2) {
        printf("-1\n");
        return 0;
    }
    for (i=0; i<=n; i++) for (r=0; r<=R; r++) for (g=0; g<=G; g++) for (k=0; k<3; k++) dp[i][r][g][k] = inf;
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (i=0; i<n; i++) {
        for (r=0; r<=min(R, i); r++) {
            for (g=0; g<=min(G, i-r); g++) {
                y = i - r - g;
                if (y > Y) continue;
                for (k=0; k<3; k++) {
                    if (r < R && k != 0)
                        dp[i+1][r+1][g][0] = min(dp[i+1][r+1][g][0], dp[i][r][g][k] + abs(inv[0][r+1][1]-g) + abs(inv[0][r+1][2]-y));
                    if (g < G && k != 1)
                        dp[i+1][r][g+1][1] = min(dp[i+1][r][g+1][1], dp[i][r][g][k] + abs(inv[1][g+1][0]-r) + abs(inv[1][g+1][2]-y));
                    if (y < Y && k != 2)
                        dp[i+1][r][g][2] = min(dp[i+1][r][g][2], dp[i][r][g][k] + abs(inv[2][y+1][0]-r) + abs(inv[2][y+1][1]-g));
                }
            }
        }
    }
    printf("%d\n", min({dp[n][R][G][0], dp[n][R][G][1], dp[n][R][G][2]}) / 2);
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~

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