Submission #876965

#	Time	Username	Problem	Language	Result	Execution time	Memory
876965		parlimoos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	331 ms	763624 KiB

joi2019_ho_t3

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n;
vector<int> s;
int dp[402][402][402][3];
vector<int> is[3];
int infs[400][3];

void f(int c0 , int c1 , int c2 , int rel){
    arr(3) cnt = {c0 , c1 , c2};
    int len = n - c0 - c1 - c2;
    int inx , hrkt;
    int res = 0;
    if(is[rel].empty() or (int)is[rel].size() <= cnt[rel]){
        res = -2;
    }else{
        if(len == 1) res = 0;
        else{
            inx = is[rel][(int)is[rel].size() - cnt[rel] - 1];
            hrkt = max(0 , infs[inx][0] - c0) + max(0 , infs[inx][1] - c1) + max(0 , infs[inx][2] - c2) - 1;
            // cout << infs[inx][0] << " " << infs[inx][1] << " " << infs[inx][2] << " :: " << hrkt << "..\n";

            cnt[rel]++;
            res = (int)1e9;
            for(int i = 0 ; i < 3 ; i++){
                if(i == rel) continue;
                if(dp[cnt[0]][cnt[1]][cnt[2]][i] == -1){
                    f(cnt[0] , cnt[1] , cnt[2] , i);
                }
                // if(c0 == 0 and c1 == 0 and c2 == 0 and rel == 2) cout << cnt[0] << " " << cnt[1] << " " << cnt[2] << " , " << i << "##\n";
                if(dp[cnt[0]][cnt[1]][cnt[2]][i] != -2) res = min(res , hrkt + dp[cnt[0]][cnt[1]][cnt[2]][i]);
            }
            if(res == (int)1e9) res = -2;
        }
    }
    dp[c0][c1][c2][rel] = res;
    // cout << c0 << " " << c1 << " " << c2 << " , " << rel << " , " << res << "::\n" << flush;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    fill(&dp[0][0][0][0] , &dp[401][401][401][3] , -1);
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        char d;
        cin >> d;
        int dd = 0;
        if(d == 'R') dd = 1;
        else if(d == 'Y') dd = 2;
        is[dd].pb(i);
        s.pb(dd);
    }
    infs[n - 1][s.back()] = 1;
    for(int i = n - 2 ; i >= 0 ; i--){
        infs[i][s[i]] = 1;
        infs[i][0] += infs[i + 1][0];
        infs[i][1] += infs[i + 1][1];
        infs[i][2] += infs[i + 1][2];
    }

    arr(3) allcnt = {0 , 0 , 0};
    for(int i = 0 ; i < 3 ; i++) f(allcnt[0] , allcnt[1] , allcnt[2] , i);

    int o = (int)1e9;
    for(int i = 0 ; i < 3 ; i++) if(dp[allcnt[0]][allcnt[1]][allcnt[2]][i] != -2) o = min(o , dp[allcnt[0]][allcnt[1]][allcnt[2]][i]);
    if(o == (int)1e9) cout << "-1";
    else cout << o;
}

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