oj.uz

Submission #961637

# Submission time Handle Problem Language Result Execution time Memory
961637 2024-04-12T09:22:04 Z BhavayGoyal Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 1040724 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 = 405;
int n, arr[N], dp[N][N][N][4], countPrev[4][N];
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()) {
                int p = pos[j][red-1];
                cost = max(0, countPrev[2][p] -  green) + max(0, countPrev[3][p] -  yellow);
            }
        }
        if (j == 2) {
            green++;
            if (green-1 < pos[j].size()) {
                int p = pos[j][green-1];
                cost = max(0, countPrev[1][p] -  red) + max(0, countPrev[3][p] -  yellow);                
            }
        } 
        if (j == 3) {
            yellow++;
            if (yellow-1 < pos[j].size()) {
                int p = pos[j][yellow-1];
                cost = max(0, countPrev[2][p] -  green) + max(0, countPrev[1][p] -  red);
            }
        }
        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);
        countPrev[arr[i+1]][i+1] = 1;
    }

    for (int j = 1; j <= 3; j++) {
        for (int i = 1; i <= n; i++) {
            countPrev[j][i] += countPrev[j][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()) {
      |                 ~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if (green-1 < pos[j].size()) {
      |                 ~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if (yellow-1 < pos[j].size()) {
      |                 ~~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:77:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   77 |         if (j == 1) red--; if (j == 2) green--; if (j == 3) yellow--;
      |         ^~
joi2019_ho_t3.cpp:77:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   77 |         if (j == 1) red--; if (j == 2) green--; if (j == 3) yellow--;
      |                            ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 554 ms 1040212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 554 ms 1040212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 1040360 KB Output is correct
2 Correct 409 ms 1040468 KB Output is correct
3 Correct 378 ms 1040476 KB Output is correct
4 Correct 417 ms 1040724 KB Output is correct
5 Correct 466 ms 1040724 KB Output is correct
6 Correct 406 ms 1040720 KB Output is correct
7 Correct 406 ms 1040476 KB Output is correct
8 Correct 473 ms 1040340 KB Output is correct
9 Correct 398 ms 1040480 KB Output is correct
10 Correct 451 ms 1040484 KB Output is correct
11 Correct 492 ms 1040480 KB Output is correct
12 Correct 280 ms 1040464 KB Output is correct
13 Correct 280 ms 1040464 KB Output is correct
14 Correct 319 ms 1040672 KB Output is correct
15 Correct 395 ms 1040696 KB Output is correct
16 Correct 388 ms 1040464 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 554 ms 1040212 KB Time limit exceeded
2 Halted 0 ms 0 KB -