oj.uz

Submission #961576

# Submission time Handle Problem Language Result Execution time Memory
961576 2024-04-12T08:25:00 Z BhavayGoyal Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 436 ms 1010180 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T> using oset = 
            tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define ar array
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define endl "\n"

const int MOD = 1e9+7;
const int inf = 1e9;
const ll linf = 1e18;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


// -------------------------------------------------- Main Code --------------------------------------------------

/*
YRGGRRGGYY

dp[i][red][green][yellow][prevCol] = dp[i+1][]

RYRGY
*/

const int N = 401;
int n, arr[N], dp[N][N][N][4];
vi pos[4];

int sol(int red, int green, int yellow, int prev) {
    int idx = (red+green+yellow+1);
    if (idx == n+1) return 0;
    if (dp[red][green][yellow][prev] != -1) return dp[red][green][yellow][prev];
    int ans = inf;
    for (int j = 1; j <= 3; j++) {
        if (j == prev) continue;
        int cost = inf;
        if (j == 1) {
            red++;
            if (red-1 < pos[j].size()) cost = max(0, pos[j][red-1] - idx);
        }
        if (j == 2) {
            green++;
            if (green-1 < pos[j].size()) cost = max(0, pos[j][green-1] - idx);
        } 
        if (j == 3) {
            yellow++;
            if (yellow-1 < pos[j].size()) cost = max(0, pos[j][yellow-1] - idx);
        }
        ans = min(ans, sol(red, green, yellow, j) + cost);
        if (j == 1) red--; if (j == 2) green--; if (j == 3) yellow--;
    }
    return dp[red][green][yellow][prev] = ans;
}

void sol() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    string s; cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') arr[i+1] = 1;
        if (s[i] == 'G') arr[i+1] = 2;
        if (s[i] == 'Y') arr[i+1] = 3;
        pos[arr[i+1]].pb(i+1);
    }

    int ans = sol(0, 0, 0, 0);
    cout << (ans==inf?-1:ans) << endl;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int sol(int, int, int, int)':
joi2019_ho_t3.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             if (red-1 < pos[j].size()) cost = max(0, pos[j][red-1] - idx);
      |                 ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:61:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if (green-1 < pos[j].size()) cost = max(0, pos[j][green-1] - idx);
      |                 ~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (yellow-1 < pos[j].size()) cost = max(0, pos[j][yellow-1] - idx);
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |         if (j == 1) red--; if (j == 2) green--; if (j == 3) yellow--;
      |         ^~
joi2019_ho_t3.cpp:68:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |         if (j == 1) red--; if (j == 2) green--; if (j == 3) yellow--;
      |                            ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 1009816 KB Output is correct
2 Correct 214 ms 1009844 KB Output is correct
3 Correct 256 ms 1009868 KB Output is correct
4 Correct 213 ms 1009700 KB Output is correct
5 Correct 219 ms 1009748 KB Output is correct
6 Correct 209 ms 1009864 KB Output is correct
7 Correct 215 ms 1009924 KB Output is correct
8 Correct 209 ms 1009928 KB Output is correct
9 Correct 207 ms 1009832 KB Output is correct
10 Correct 220 ms 1009688 KB Output is correct
11 Incorrect 212 ms 1009920 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 1009816 KB Output is correct
2 Correct 214 ms 1009844 KB Output is correct
3 Correct 256 ms 1009868 KB Output is correct
4 Correct 213 ms 1009700 KB Output is correct
5 Correct 219 ms 1009748 KB Output is correct
6 Correct 209 ms 1009864 KB Output is correct
7 Correct 215 ms 1009924 KB Output is correct
8 Correct 209 ms 1009928 KB Output is correct
9 Correct 207 ms 1009832 KB Output is correct
10 Correct 220 ms 1009688 KB Output is correct
11 Incorrect 212 ms 1009920 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 213 ms 1009744 KB Output is correct
2 Correct 418 ms 1009892 KB Output is correct
3 Correct 403 ms 1010032 KB Output is correct
4 Correct 432 ms 1009744 KB Output is correct
5 Correct 403 ms 1009844 KB Output is correct
6 Correct 414 ms 1009816 KB Output is correct
7 Correct 432 ms 1009840 KB Output is correct
8 Correct 436 ms 1009748 KB Output is correct
9 Correct 405 ms 1009972 KB Output is correct
10 Correct 417 ms 1010000 KB Output is correct
11 Correct 392 ms 1009780 KB Output is correct
12 Correct 246 ms 1010180 KB Output is correct
13 Correct 268 ms 1009744 KB Output is correct
14 Correct 328 ms 1009744 KB Output is correct
15 Correct 426 ms 1009744 KB Output is correct
16 Correct 394 ms 1009804 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 1009816 KB Output is correct
2 Correct 214 ms 1009844 KB Output is correct
3 Correct 256 ms 1009868 KB Output is correct
4 Correct 213 ms 1009700 KB Output is correct
5 Correct 219 ms 1009748 KB Output is correct
6 Correct 209 ms 1009864 KB Output is correct
7 Correct 215 ms 1009924 KB Output is correct
8 Correct 209 ms 1009928 KB Output is correct
9 Correct 207 ms 1009832 KB Output is correct
10 Correct 220 ms 1009688 KB Output is correct
11 Incorrect 212 ms 1009920 KB Output isn't correct
12 Halted 0 ms 0 KB -