oj.uz

Submission #1087916

# Submission time Handle Problem Language Result Execution time Memory
1087916 2024-09-13T13:26:31 Z efishel Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 500 ms 768936 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

vi ou[3];
int dp[403][403][403][3]; // dp[a][b][c][last] = min operations to have a valid string\
rn having a prefix of length a+b+c having taken a as, b bs, and c cs, having the last color as last

ll n;
int bey[3]; // bey[i] = how many taken are beyond the last taken of color i
int ptr[3][3];
// bool taken[403];
int solve (ll a, ll b, ll c, ll last) { // have taken the first a as b bs and c cs, the last rn is last
    if (a+b+c == n) return 0;
    if (dp[a][b][c][last] <= 1e9) return dp[a][b][c][last];
    int &ans = dp[a][b][c][last];
    ans = 1e9;
    int i = a+b+c;
    // ll lsa = a < ou[0].size() ? ou[0][a] : n;
    // ll lsb = b < ou[1].size() ? ou[1][b] : n;
    // ll lsc = c < ou[2].size() ? ou[2][c] : n;
    auto costFor = [&](ll col, ll t) {
        int ans = 0;
        for (ll j = 0; j < a; j++) if (ou[0][j] < ou[col][t]) ans++;
        for (ll j = 0; j < b; j++) if (ou[1][j] < ou[col][t]) ans++;
        for (ll j = 0; j < c; j++) if (ou[2][j] < ou[col][t]) ans++;
        return ans;
    };
    if (last != 0 && a < ou[0].size()) { ans = min(ans, solve(a+1, b, c, 0) + ou[0][a] - costFor(0, a)); }
    if (last != 1 && b < ou[1].size()) { ans = min(ans, solve(a, b+1, c, 1) + ou[1][b] - costFor(1, b)); }
    if (last != 2 && c < ou[2].size()) { ans = min(ans, solve(a, b, c+1, 2) + ou[2][c] - costFor(2, c)); }
    return ans;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n;
    string str;
    cin >> str;
    memset(dp, 0x3f, sizeof(dp));
    // ou[0] = ou[1] = ou[2] = { -1 };
    for (ll i = 0; i < n; i++) {
        ou[(str[i] == 'R' ? 0 : str[i] == 'G' ? 1 : 2)].push_back(i);
    }
    ll ans = min({ solve(0, 0, 0, 0), solve(0, 0, 0, 1), solve(0, 0, 0, 2) });
    cout << (ans == 1e9 ? -1 : ans) << '\n';
    return 0;
}

Compilation message

joi2019_ho_t3.cpp:8:27: warning: multi-line comment [-Wcomment]
    8 | int dp[403][403][403][3]; // dp[a][b][c][last] = min operations to have a valid string\
      |                           ^
joi2019_ho_t3.cpp: In function 'int solve(ll, ll, ll, ll)':
joi2019_ho_t3.cpp:31:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if (last != 0 && a < ou[0].size()) { ans = min(ans, solve(a+1, b, c, 0) + ou[0][a] - costFor(0, a)); }
      |                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     if (last != 1 && b < ou[1].size()) { ans = min(ans, solve(a, b+1, c, 1) + ou[1][b] - costFor(1, b)); }
      |                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:33:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if (last != 2 && c < ou[2].size()) { ans = min(ans, solve(a, b, c+1, 2) + ou[2][c] - costFor(2, c)); }
      |                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:20:9: warning: unused variable 'i' [-Wunused-variable]
   20 |     int i = a+b+c;
      |         ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 768848 KB Output is correct
2 Correct 340 ms 768852 KB Output is correct
3 Correct 350 ms 768740 KB Output is correct
4 Correct 351 ms 768916 KB Output is correct
5 Execution timed out 546 ms 768852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 768848 KB Output is correct
2 Correct 340 ms 768852 KB Output is correct
3 Correct 350 ms 768740 KB Output is correct
4 Correct 351 ms 768916 KB Output is correct
5 Execution timed out 546 ms 768852 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 768816 KB Output is correct
2 Correct 353 ms 768936 KB Output is correct
3 Correct 324 ms 768852 KB Output is correct
4 Correct 333 ms 768824 KB Output is correct
5 Correct 334 ms 768852 KB Output is correct
6 Correct 336 ms 768848 KB Output is correct
7 Correct 351 ms 768848 KB Output is correct
8 Correct 348 ms 768852 KB Output is correct
9 Correct 370 ms 768852 KB Output is correct
10 Correct 346 ms 768848 KB Output is correct
11 Correct 350 ms 768920 KB Output is correct
12 Correct 377 ms 768848 KB Output is correct
13 Correct 368 ms 768848 KB Output is correct
14 Correct 341 ms 768852 KB Output is correct
15 Correct 339 ms 768848 KB Output is correct
16 Correct 332 ms 768848 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 768848 KB Output is correct
2 Correct 340 ms 768852 KB Output is correct
3 Correct 350 ms 768740 KB Output is correct
4 Correct 351 ms 768916 KB Output is correct
5 Execution timed out 546 ms 768852 KB Time limit exceeded
6 Halted 0 ms 0 KB -