Submission #684631

#	Time	Username	Problem	Language	Result	Execution time	Memory
684631		vicious	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	397 ms	776096 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 410, INF=2e9;
int n, s[N];
int dp[N][N][N][3];
int pref[3][N], pos[3][N];
int rc,gc,yc;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        char x; cin >> x;
        if (x=='R') s[i]=0,++rc,pos[0][rc]=i;
        else if (x=='G') s[i]=1,++gc,pos[1][gc]=i;
        else s[i]=2,++yc,pos[2][yc]=i;
        pref[0][i]=rc;
        pref[1][i]=gc;
        pref[2][i]=yc;
    }
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                fill(dp[i][j][k],dp[i][j][k]+3,INF);
            }
        }
    }   
    for (int i = 0; i < 3; ++i) dp[0][0][0][i]=0;
    for (int i = 0; i <= rc; ++i) {
        for (int j = 0; j <= gc; ++j) {
            for (int k = 0; k <= yc; ++k) {
                if (i==0&&j==0&k==0) continue;
                if (i) { // place red 
                    int og = pos[0][i];
                    dp[i][j][k][0]=min(dp[i-1][j][k][1],dp[i-1][j][k][2]);
                    dp[i][j][k][0]+=max(0, pref[1][og]-j)+max(0, pref[2][og]-k);
                }
                if (j) {
                    int og = pos[1][j];
                    dp[i][j][k][1]=min(dp[i][j-1][k][0],dp[i][j-1][k][2]);
                    dp[i][j][k][1]+=max(0, pref[0][og]-i)+max(0, pref[2][og]-k);   
                }
                if (k) {
                    int og = pos[2][k];
                    dp[i][j][k][2]=min(dp[i][j][k-1][0],dp[i][j][k-1][1]);
                    dp[i][j][k][2]+=max(0, pref[0][og]-i)+max(0, pref[1][og]-j);
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 3; ++i) chmin(ans, dp[rc][gc][yc][i]);
    cout << (ans==INF?-1:ans);
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:45:28: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   45 |                 if (i==0&&j==0&k==0) continue;
      |                           ~^~~

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