Submission #129104

#	Time	Username	Problem	Language	Result	Execution time	Memory
129104		miguel	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	127 ms	163136 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int n, dp[405][405][405][3], cnt[3];
string s;
vector<pii> v[3];

int get(char c){
    if(c=='R') return 0;
    else if(c=='G') return 1;
    else return 2;
}

int dst(pii a, pii b){
    return abs(a.x-b.x)+abs(a.y.x-b.y.x)+abs(a.y.y-b.y.y);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>s;
    for(int i=0; i<n; i++){
        int x=get(s[i]);
        cnt[x]++;
        v[x].pb({cnt[0], {cnt[1], cnt[2]}});
    }
    int rr=v[0].sz, gg=v[1].sz, yy=v[2].sz;
    if(max(rr, max(gg, yy))>(n+1)/2) return cout<<"-1", 0;
    for(int r=0; r<=rr; r++){
        for(int g=0; g<=gg; g++){
            for(int y=0; y<=yy; y++){
                int sum=r+g+y;
                if(sum==0) continue;
                dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=1e9;
                if(r) dp[r][g][y][0]=min(dp[r-1][g][y][1], dp[r-1][g][y][2])+dst(v[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])+dst(v[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])+dst(v[2][y-1], {r, {g, y}});
            }
        }
    }
    cout<<min(dp[rr][gg][yy][0], min(dp[rr][gg][yy][1], dp[rr][gg][yy][2]))/2;
}

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