Submission #1248846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248846		wedonttalkanymore	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	125 ms	76104 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 1 << 16;

int n;
string s;
vector<int> pos[4];
vector<ll> pref;
int nr, ng, ny;
vector<ll> f;

int idx(int i, int j, int k, int last) {
    return (((i * (ng + 1) + j) * (ny + 1) + k) << 2) | last;
}

ll dp(int i, int j, int k, int last) {
    int id = idx(i, j, k, last);
    if (f[id] != -1) return f[id];
    ll &r = f[id];
    if (i == nr && j == ng && k == ny) return r = 0;
    r = inf;
    if (last != 1 && i < nr) {
        int x = pos[1][i + 1];
        ll cost = max(0LL, pref[x * 4 + 2] - j) + max(0LL, pref[x * 4 + 3] - k);
        r = min(r, dp(i + 1, j, k, 1) + cost);
    }
    if (last != 2 && j < ng) {
        int x = pos[2][j + 1];
        ll cost = max(0LL, pref[x * 4 + 1] - i) + max(0LL, pref[x * 4 + 3] - k);
        r = min(r, dp(i, j + 1, k, 2) + cost);
    }
    if (last != 3 && k < ny) {
        int x = pos[3][k + 1];
        ll cost = max(0LL, pref[x * 4 + 1] - i) + max(0LL, pref[x * 4 + 2] - j);
        r = min(r, dp(i, j, k + 1, 3) + cost);
    }
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }

    cin >> n >> s;
    s = "#" + s;
    pref.assign((n + 1) * 4, 0);
    for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= 3; c++) pref[i * 4 + c] = pref[(i - 1) * 4 + c];
        if (s[i] == 'R') pos[1].push_back(i), pref[i * 4 + 1]++;
        if (s[i] == 'G') pos[2].push_back(i), pref[i * 4 + 2]++;
        if (s[i] == 'Y') pos[3].push_back(i), pref[i * 4 + 3]++;
    }

    pos[1].insert(pos[1].begin(), 0);
    pos[2].insert(pos[2].begin(), 0);
    pos[3].insert(pos[3].begin(), 0);
    nr = pos[1].size() - 1;
    ng = pos[2].size() - 1;
    ny = pos[3].size() - 1;
    f.assign((nr + 1) * (ng + 1) * (ny + 1) * 4, -1);
    ll ans = min({dp(0, 0, 0, 1), dp(0, 0, 0, 2), dp(0, 0, 0, 3)});
    cout << (ans >= inf ? -1 : ans);
    return 0;
}

Compilation message (stderr)

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

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