Submission #1075686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075686		dosts	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	3 ms	1412 KiB

joi2019_ho_t3

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e7;
const int N = 5001;

void solve() { 
    int n;
    cin >> n;
    string s;
    cin >> s;
    vi as,bs,cs;
    as.push_back(0),bs.push_back(0),cs.push_back(0);
    for (int i=0;i<n;i++) {
        if (s[i] == 'R') as.push_back(i+1);
        else if (s[i] == 'G') bs.push_back(i+1);
        else cs.push_back(i+1);
    }
    auto cost = [&](int a,int b,int c,int p) {
        int pos;
        if (p == 0) pos = as[a];
        else if (p == 1) pos = bs[b];
        else pos = cs[c];
        int curpos = a+b+c;
        //cout << pos sp curpos << endl;
        if (pos < curpos) return 0;
        return pos-curpos;
    };
    int sa = as.size(),sb = bs.size(),sc = cs.size();
    int dp[sa+1][sb+1][sc+1][3];
    for (int i=0;i<=sa;i++) for (int ii=0;ii<=sb;ii++) for (int iii=0;iii<=sc;iii++) for (int p=0;p<3;p++) dp[i][ii][iii][p] = inf;
    dp[1][0][0][0] = as[1]-1;
    dp[0][1][0][1] = bs[1]-1;
    dp[0][0][1][2] = cs[1]-1;
    for (int a=0;a<=sa-1;a++) {
        for (int b=0;b<=sb-1;b++) {
            for (int c=0;c<=sc-1;c++) {
                if ((a+b+c) <= 1) continue;
                vi dims{a,b,c};
                for (int p=0;p<3;p++) {
                    dp[a][b][c][p] = inf;
                    if (!dims[p]) continue;
                    dims[p]--;
                    int costy = cost(a,b,c,p);
                    for (int pp=0;pp<3;pp++) {
                        if (p == pp) continue;
                        if (dp[dims[0]][dims[1]][dims[2]][pp] >= inf) continue;
                        dp[a][b][c][p] = min(dp[a][b][c][p],
                        dp[dims[0]][dims[1]][dims[2]][pp]+costy);
                    }
                    dims[p]++;
                }
            }
        } 
    }
    int ans = min({dp[sa-1][sb-1][sc-1][0],
                 dp[sa-1][sb-1][sc-1][1],      
                 dp[sa-1][sb-1][sc-1][2]});
    if (ans >= inf) cout << -1 << endl;
    else cout << ans << endl;
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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