Submission #117475

#	Time	Username	Problem	Language	Result	Execution time	Memory
117475		songc	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	284 ms	258456 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N;
char str[440];
vector<int> R, G, Y;
int D[4][404][404][404];

int f(int l, int r, int g, int y){
    if (r+g+y >= N) return 0;
    if ((int)R.size()-r > (int)G.size()-g+(int)Y.size()-y+1) return INF;
    if ((int)G.size()-g > (int)R.size()-r+(int)Y.size()-y+1) return INF;
    if ((int)Y.size()-y > (int)R.size()-r+(int)G.size()-g+1) return INF;
    if (D[l][r][g][y] != INF) return D[l][r][g][y];
    if (l != 0 && r < (int)R.size()){
        int ret = f(0, r+1, g, y);
        ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), R[r]) - G.begin()));
        ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), R[r]) - Y.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    if (l != 1 && g < (int)G.size()){
        int ret = f(1, r, g+1, y);
        ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), G[g]) - R.begin()));
        ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), G[g]) - Y.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    if (l != 2 && y < (int)Y.size()){
        int ret = f(2, r, g, y+1);
        ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), Y[y]) - R.begin()));
        ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), Y[y]) - G.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    return D[l][r][g][y];
}

int main(){
    scanf("%d", &N);
    scanf("%s", str+1);
    for (int i=1; i<=N; i++){
        if (str[i] == 'R') R.push_back(i);
        else if (str[i] == 'G') G.push_back(i);
        else Y.push_back(i);
    }
    for (int i=0; i<4; i++){
        for (int j=0; j<=(int)R.size(); j++){
            for (int k=0; k<=(int)G.size(); k++){
                for (int l=0; l<=(int)Y.size(); l++){
                    D[i][j][k][l] = INF;
                }
            }
        }
    }
    int ans = f(3, 0, 0, 0);
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:41: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:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str+1);
     ~~~~~^~~~~~~~~~~~~

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