Submission #153891

#	Time	Username	Problem	Language	Result	Execution time	Memory
153891		mhy908	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	145 ms	163080 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
int n, dp[410][410][410][3], cnt[3];
char str[410];
vector<pair<int, pii> > vc[3];
int dist(pair<int, pii> a, pair<int, pii> b)
{
    return abs(a.F-b.F)+abs(a.S.F-b.S.F)+abs(a.S.S-b.S.S);
}
int main()
{
    scanf("%d", &n);
    scanf("%s", str);
    for(int i=0; i<n; i++){
        int c;
        if(str[i]=='R')c=0;
        else if(str[i]=='G')c=1;
        else c=2;
        cnt[c]++;
        vc[c].pb(mp(cnt[0], mp(cnt[1], cnt[2])));
    }
    int red=vc[0].size(), green=vc[1].size(), yellow=vc[2].size();
    if(max(red, max(green, yellow))>(n+1)/2){
        printf("-1");
        return 0;
    }
    for(int r=0; r<=red; r++){
        for(int g=0; g<=green; g++){
            for(int y=0; y<=yellow; y++){
                if(r+g+y==0)continue;
                dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=inf;
                if(r)dp[r][g][y][0]=min(dp[r-1][g][y][1], dp[r-1][g][y][2])+dist(vc[0][r-1], {r, {g, y}});
                if(g)dp[r][g][y][1]=min(dp[r][g-1][y][2], dp[r][g-1][y][0])+dist(vc[1][g-1], {r, {g, y}});
                if(y)dp[r][g][y][2]=min(dp[r][g][y-1][0], dp[r][g][y-1][1])+dist(vc[2][y-1], {r, {g, y}});
            }
        }
    }
    printf("%d", min(dp[red][green][yellow][0], min(dp[red][green][yellow][1], dp[red][green][yellow][2]))/2);
}

Compilation message (stderr)

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

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