oj.uz

Submission #1087627

# Submission time Handle Problem Language Result Execution time Memory
1087627 2024-09-13T03:19:40 Z efishel Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 408 ms 769104 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

vll 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 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;
    ll i = a+b+c;
    if (last != 0 && a < ou[0].size()) { ans = min(ans, solve(a+1, b, c, 0) + (int)max(0LL, ou[0][a]-i)); }
    if (last != 1 && b < ou[1].size()) { ans = min(ans, solve(a, b+1, c, 1) + (int)max(0LL, ou[1][b]-i)); }
    if (last != 2 && c < ou[2].size()) { ans = min(ans, solve(a, b, c+1, 2) + (int)max(0LL, ou[2][c]-i)); }
    return ans;
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n;
    string str;
    cin >> str;
    memset(dp, 0x3f, sizeof(dp));
    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:7:27: warning: multi-line comment [-Wcomment]
    7 | 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:17:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if (last != 0 && a < ou[0].size()) { ans = min(ans, solve(a+1, b, c, 0) + (int)max(0LL, ou[0][a]-i)); }
      |                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     if (last != 1 && b < ou[1].size()) { ans = min(ans, solve(a, b+1, c, 1) + (int)max(0LL, ou[1][b]-i)); }
      |                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if (last != 2 && c < ou[2].size()) { ans = min(ans, solve(a, b, c+1, 2) + (int)max(0LL, ou[2][c]-i)); }
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 768848 KB Output is correct
2 Correct 353 ms 768928 KB Output is correct
3 Correct 345 ms 768848 KB Output is correct
4 Correct 348 ms 768848 KB Output is correct
5 Correct 356 ms 768852 KB Output is correct
6 Correct 354 ms 768884 KB Output is correct
7 Correct 341 ms 768716 KB Output is correct
8 Correct 357 ms 768848 KB Output is correct
9 Correct 348 ms 768852 KB Output is correct
10 Correct 360 ms 769000 KB Output is correct
11 Incorrect 360 ms 768864 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 768848 KB Output is correct
2 Correct 353 ms 768928 KB Output is correct
3 Correct 345 ms 768848 KB Output is correct
4 Correct 348 ms 768848 KB Output is correct
5 Correct 356 ms 768852 KB Output is correct
6 Correct 354 ms 768884 KB Output is correct
7 Correct 341 ms 768716 KB Output is correct
8 Correct 357 ms 768848 KB Output is correct
9 Correct 348 ms 768852 KB Output is correct
10 Correct 360 ms 769000 KB Output is correct
11 Incorrect 360 ms 768864 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 768824 KB Output is correct
2 Correct 358 ms 768848 KB Output is correct
3 Correct 349 ms 768848 KB Output is correct
4 Correct 344 ms 768940 KB Output is correct
5 Correct 353 ms 768712 KB Output is correct
6 Correct 352 ms 768852 KB Output is correct
7 Correct 348 ms 768820 KB Output is correct
8 Correct 338 ms 768852 KB Output is correct
9 Correct 360 ms 769104 KB Output is correct
10 Correct 348 ms 768752 KB Output is correct
11 Correct 408 ms 768848 KB Output is correct
12 Correct 350 ms 768756 KB Output is correct
13 Correct 343 ms 768784 KB Output is correct
14 Correct 349 ms 768908 KB Output is correct
15 Correct 358 ms 768852 KB Output is correct
16 Correct 359 ms 768852 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 768848 KB Output is correct
2 Correct 353 ms 768928 KB Output is correct
3 Correct 345 ms 768848 KB Output is correct
4 Correct 348 ms 768848 KB Output is correct
5 Correct 356 ms 768852 KB Output is correct
6 Correct 354 ms 768884 KB Output is correct
7 Correct 341 ms 768716 KB Output is correct
8 Correct 357 ms 768848 KB Output is correct
9 Correct 348 ms 768852 KB Output is correct
10 Correct 360 ms 769000 KB Output is correct
11 Incorrect 360 ms 768864 KB Output isn't correct
12 Halted 0 ms 0 KB -