Submission #1099281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099281		underwaterkillerwhale	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	84 ms	5312 KiB

joi2019_ho_t3

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 4e2 + 7;
int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

inline void minimize (int &A, int B) {
    if (A > B) A = B;
}

int n;
int a[N];
vector<int> pos[5];
int szC[5];
int pre[5][N];
int dp[2][N][N][5]; ///0, 1

int cost (int cur, int p0, int p1, int p2) {
    return max(0, pre[0][cur] - pre[0][p0]) + max(0, pre[1][cur] - pre[1][p1]) + max(0, pre[2][cur] - pre[2][p2]);
}

void solution () {
    cin >> n;
    string S;
    cin >> S;
    rep (i, 0, 2) pos[i].pb(0);
    rep (i, 1, n) {
        a[i] = (S[i - 1] == 'R' ? 0 : (S[i - 1] == 'G' ? 1 : 2));
        pos[a[i]].pb(i);
        szC[a[i]]++;
    }
    rep (j, 0, 2)
    rep (i, 1, n) {
        pre[j][i] = pre[j][i - 1] + (a[i] == j);
    }
    rep (j, 0, szC[0])
    rep (k, 0, szC[1])
    rep (t, 0, 2) dp[0][j][k][t] = INF;

    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    dp[0][0][0][0] = 0;
    rep (i, 0, n) {
        rep (j, 0, szC[0])
        rep (k, 0, szC[1])
        rep (t, 0, 2) dp[i & 1 ^ 1][j][k][t] = INF;
        rep (j, 0, szC[0])
        rep (k, 0, szC[1]) {
            int p = i - j - k;
//            cout << i<<","<<j<<","<<k<<","<<p<<"\n";
            if (j + k > i || p > szC[2])
                continue;
            rep (t, 0, 2) {
                if (j < szC[0] && t != 0) {
                    minimize (dp[i & 1 ^ 1][j + 1][k][0], dp[i & 1][j][k][t] + cost (pos[0][j + 1], pos[0][j + 1], pos[1][k], pos[2][p]) );
                }
                if (k < szC[1] && t != 1) {
                    minimize (dp[i & 1 ^ 1][j][k + 1][1], dp[i & 1][j][k][t] + cost (pos[1][k + 1], pos[0][j], pos[1][k + 1], pos[2][p]) );
                }
                if (p < szC[2] && t != 2) {
                    minimize (dp[i & 1 ^ 1][j][k][2], dp[i & 1][j][k][t] + cost (pos[2][p + 1], pos[0][j], pos[1][k], pos[2][p + 1]) );
                }
            }
        }
    }
    int res = INF;
    rep (i, 0, 2) res = min(res, dp[n & 1][szC[0]][szC[1]][i]);
    if (res > n * n) cout << -1;
    else cout << res <<"\n";

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +10

5 5
01101
10001
00110
10101
00100
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void solution()':
joi2019_ho_t3.cpp:67:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   67 |         rep (t, 0, 2) dp[i & 1 ^ 1][j][k][t] = INF;
      |                          ~~^~~
joi2019_ho_t3.cpp:76:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   76 |                     minimize (dp[i & 1 ^ 1][j + 1][k][0], dp[i & 1][j][k][t] + cost (pos[0][j + 1], pos[0][j + 1], pos[1][k], pos[2][p]) );
      |                                  ~~^~~
joi2019_ho_t3.cpp:79:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   79 |                     minimize (dp[i & 1 ^ 1][j][k + 1][1], dp[i & 1][j][k][t] + cost (pos[1][k + 1], pos[0][j], pos[1][k + 1], pos[2][p]) );
      |                                  ~~^~~
joi2019_ho_t3.cpp:82:36: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   82 |                     minimize (dp[i & 1 ^ 1][j][k][2], dp[i & 1][j][k][t] + cost (pos[2][p + 1], pos[0][j], pos[1][k], pos[2][p + 1]) );
      |                                  ~~^~~

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