Submission #538610

#	Time	Username	Problem	Language	Result	Execution time	Memory
538610		79brue	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	165 ms	6092 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[402];
int DP[2][402][402][3];
int cnt[3];
vector<int> occ[3];

int weight[402][402][3]; /// index, 배열에서의 순서

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        arr[i] = c=='R' ? 0 : c=='G' ? 1 : 2;
        cnt[arr[i]]++;
        occ[arr[i]].push_back(i);
    }

    for(int i=1; i<=n; i++){
        for(int d=0; d<3; d++){
            for(int j=1; j<=cnt[d]; j++){
                weight[i][j][d] = weight[i-1][j][d] + (arr[i] == d && i <= occ[d][j-1]);
            }
        }
    }

    for(int i=0; i<2; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) for(int l=0; l<3; l++) DP[i][j][k][l]=1e9;
    DP[0][0][0][0] = DP[0][0][0][1] = DP[0][0][0][2] = 0;

    for(int i=1; i<=n; i++){
        int ri = i%2;
        for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) for(int l=0; l<3; l++) DP[ri][j][k][l]=1e9;

        for(int j=0; j<i && j<=cnt[0]; j++){
            for(int k=0; j+k<i && k<=cnt[1]; k++){
                int l = i-j-k-1;
                if(l>cnt[2]) continue;
                for(int d=0; d<3; d++){
//                    printf("%d %d %d %d %d: %d\n", i, j, k, l, d, DP[!ri][j][k][d]);
                    if(j<cnt[0] && d!=0){
                        int w = occ[0][j];
                        DP[ri][j+1][k][0] = min(DP[ri][j+1][k][0],
                                                DP[!ri][j][k][d] + w-1 -
                                                (weight[w][j][0] + weight[w][k][1] + weight[w][l][2]));
                    }
                    if(k<cnt[1] && d!=1){
                        int w = occ[1][k];
                        DP[ri][j][k+1][1] = min(DP[ri][j][k+1][1],
                                                DP[!ri][j][k][d] + w-1 -
                                                (weight[w][j][0] + weight[w][k][1] + weight[w][l][2]));
                    }
                    if(l<cnt[2] && d!=2){
                        int w = occ[2][l];
                        DP[ri][j][k][2] = min(DP[ri][j][k][2],
                                                DP[!ri][j][k][d] + w-1 -
                                                (weight[w][j][0] + weight[w][k][1] + weight[w][l][2]));
                    }
                }
            }
        }
    }

    int ans = 1e9;
    for(int i=0; i<3; i++) ans = min(ans, DP[n%2][cnt[0]][cnt[1]][i]);
    printf("%d", ans==1000000000 ? -1 : ans);
}

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]
   16 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~

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