oj.uz

Submission #168615

# Submission time Handle Problem Language Result Execution time Memory
168615 2019-12-14T09:54:18 Z srvlt Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 197 ms 193472 KB 
//#pragma GCC target ("avx2,sse2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree <pair <ll, int>, null_type, less <pair <ll, int> >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ull unsigned long long
#define db double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"

#define left fsdsdfoisf
#define sum dpsdfioppsf
#define assign xcvjlkdjfio
#define trie fksdfkjkfnjuiv
#define next sidlfjsfkl
#define merge sdfksdkfsldf

//#define int long long

using namespace std;

void dout() {
    cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 403, inf = 1e9;
int n, R, G, Y, dp[3][N][N][N];
string s;
vector <int> r, g, y;

void solve(int tc) {
    // check for (int i = 0; i < n; j++)
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'R') {
            r.pb(i);
        }   else if (s[i - 1] == 'G') {
            g.pb(i);
        }   else {
            y.pb(i);
        }
    }
    R = sz(r), G = sz(g), Y = sz(y);
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= min(i, R); j++) {
            for (int k = 0; k <= min(i - j, G); k++) {
                int h = i - j - k;
                if (h > Y) {
                    continue;
                }
                for (int l = 0; l < 3; l++) {
                    int res = inf;
                    if (l == 0 && j > 0) {
                        res = min(res, dp[1][j - 1][k][h]);
                        res = min(res, dp[2][j - 1][k][h]);
                        res += abs(r[j - 1] - i);
                    }   else if (l == 1 && k > 0) {
                        res = min(res, dp[0][j][k - 1][h]);
                        res = min(res, dp[2][j][k - 1][h]);
                        res += abs(g[k - 1] - i);
                    }   else if (l == 2 && h > 0) {
                        res = min(res, dp[0][j][k][h - 1]);
                        res = min(res, dp[1][j][k][h - 1]);
                        res += abs(y[h - 1] - i);
                    }
                    dp[l][j][k][h] = res;
                }
            }
        }
    }
    int res = inf;
    for (int i = 0; i < 3; i++) {
        res = min(res, dp[i][R][G][Y]);
    }
    if (res == inf) {
        cout << -1;
    }   else {
        cout << res / 2;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("meetings.in", "r", stdin);
//    freopen("meetings.out", "w", stdout);
    int tc = 1;
//    cin >> tc;
    for (int i = 0; i < tc; i++) {
        solve(i);
//        cleanup();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Incorrect 3 ms 632 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Incorrect 3 ms 632 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 2 ms 376 KB Output is correct
2 Correct 197 ms 193372 KB Output is correct
3 Correct 188 ms 192580 KB Output is correct
4 Correct 184 ms 193472 KB Output is correct
5 Correct 187 ms 193400 KB Output is correct
6 Correct 180 ms 193372 KB Output is correct
7 Correct 185 ms 192376 KB Output is correct
8 Correct 157 ms 192504 KB Output is correct
9 Correct 157 ms 191460 KB Output is correct
10 Correct 159 ms 193400 KB Output is correct
11 Correct 159 ms 193364 KB Output is correct
12 Correct 43 ms 52600 KB Output is correct
13 Correct 75 ms 91800 KB Output is correct
14 Correct 109 ms 132344 KB Output is correct
15 Correct 158 ms 193380 KB Output is correct
16 Correct 184 ms 193272 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Incorrect 3 ms 632 KB Output isn't correct
12 Halted 0 ms 0 KB -