Submission #1118925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118925		gdragon	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	369 ms	65864 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define TASK "long"
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define GETBIT(mask, i) ((mask) >> (i) & 1)
#define MASK(i) ((1LL) << (i))
#define SZ(x) ((int)(x).size())
#define mp make_pair
#define CNTBIT(mask) __builtin_popcount(mask)
template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
typedef pair<int, int> ii;
const int N = 400 + 2;
const int inf = 1e9 + 7;
const long long INF = (long long)1e18 + 7;
const int mod = 1e9 + 7;
int n;
int a[N];
string s;
void read() {
    cin >> n >> s;
    for(int i = 0; i < n; i++) {
        if (s[i] == 'R') a[i + 1] = 0;
        else if (s[i] == 'G') a[i + 1] = 1;
        else a[i + 1] = 2;
    }
}
void solve() {
    vector<int> pos[3];
    for(int i = 1; i <= n; i++) pos[a[i]].push_back(i);
    vector<vector<vector<int>>> dp[3];
    for(int i = 0; i < 3; i++) {
        dp[i].assign(SZ(pos[0]) + 1, vector<vector<int>>(SZ(pos[1]) + 1, vector<int>(SZ(pos[2]) + 1, inf)));
    }
    vector<tuple<int, int, int>> upd[n + 1];
    for(int i = 0; i <= SZ(pos[0]); i++) {
        for(int j = 0; j <= SZ(pos[1]); j++) {
            for(int z = 0; z <= SZ(pos[2]); z++) {
                // cerr << i + j + z << ' ' << i << ' ' << j << ' ' << z << endl;
                upd[i + j + z].push_back({i, j, z});
            }
        }
    }
    for(int i = 0; i < 2; i++) dp[i][0][0][0] = 0;
    auto countLess = [&](tuple<int, int, int> sz, int p) -> int {
        // return 0;
        int cnt = 0;
        int s[] = {get<0>(sz), get<1>(sz), get<2>(sz)};
        for(int i = 0; i < 3; i++) {
            int t = lower_bound(pos[i].begin(), pos[i].begin() + s[i], p) - pos[i].begin();
            cnt += s[i] - t;
        }
         // if (p == 1) cout << cnt << endl;
        // if (p == 1) cout << cnt << endl;
        return cnt;
    };
    for(int i = 0; i < n; i++) {
        for(auto j: upd[i]) {
            int c0 = get<0>(j);
            int c1 = get<1>(j);
            int c2 = get<2>(j);
            for(int last = 0; last < 3; last++) {
                if (dp[last][c0][c1][c2] < inf) {
                    // cerr << c0 << ' ' << c1 << ' ' << c2 << ' ' << last << ' ' << dp[last][c0][c1][c2] << endl;
                    tuple<int, int, int> sz = {c0, c1, c2};
                    int tmp = dp[last][c0][c1][c2];
                    if (last != 0 && c0 < SZ(pos[0])) {
                        int p = pos[0][c0];
                        int less = countLess(sz, p);
                        int cost = p + less - (i + 1);
                        minimize(dp[0][c0 + 1][c1][c2], tmp + cost);
                    }
                    if (last != 1 && c1 < SZ(pos[1])) {
                        int p = pos[1][c1];
                        int less = countLess(sz, p);
                        int cost = p + less - (i + 1);
                        minimize(dp[1][c0][c1 + 1][c2], tmp + cost);
                    }
                    if (last != 2 && c2 < SZ(pos[2])) {
                        int p = pos[2][c2];
                        int less = countLess(sz, p);
                        int cost = p + less - (i + 1);
                        minimize(dp[2][c0][c1][c2 + 1], tmp + cost);
                    }
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[i][SZ(pos[0])][SZ(pos[1])][SZ(pos[2])]);
    cout << (ans == inf ? -1 : ans);
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--) {
        read();
        solve();
    }
    return 0;
}

// rmq - rmq2d
// hash
// fw - fw2d
// segtree

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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