oj.uz

Submission #716381

# Submission time Handle Problem Language Result Execution time Memory
716381 2023-03-29T22:23:47 Z Kahou Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 1048576 KB 
/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 405;
int n, dp[N][N][N][3];
string s;
vector<int> vc[3];
vector<pii> vt[3];

void solve() {
        cin >> n;
        cin >> s;
        s = '.'+s;
        for (int i = 1; i <= n; i++) {
                int c = (s[i] != 'R') + (s[i] == 'Y');
                vc[c].push_back(i);
        }
        for (int A = 0; A < (int)vc[0].size(); A++) {
                int b = lower_bound(vc[1].begin(), vc[1].end(), vc[0][A])-vc[1].begin();
                int c = lower_bound(vc[2].begin(), vc[2].end(), vc[0][A])-vc[2].begin();
                vt[0].push_back({b, c});
        }
        for (int B = 0; B < (int)vc[1].size(); B++) {
                int a = lower_bound(vc[0].begin(), vc[0].end(), vc[1][B])-vc[0].begin();
                int c = lower_bound(vc[2].begin(), vc[2].end(), vc[1][B])-vc[2].begin();
                vt[1].push_back({a, c});
        }
        for (int C = 0; C < (int)vc[2].size(); C++) {
                int a = lower_bound(vc[0].begin(), vc[0].end(), vc[2][C])-vc[0].begin();
                int b = lower_bound(vc[1].begin(), vc[1].end(), vc[2][C])-vc[1].begin();
                vt[1].push_back({a, b});
        }
        memset(dp, 64, sizeof dp);
        dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
        for (int sum = 0; sum <= n; sum++) {
                for (int A = 0; A <= sum; A++) {
                        for (int B = 0; A+B <= sum; B++) {
                                int C = sum-A-B;
                                if (A < (int)vc[0].size()) {
                                        int b = vt[0][A].F;
                                        int c = vt[0][A].S;
                                        dp[A+1][B][C][0] = min(dp[A+1][B][C][0], min(dp[A][B][C][1], dp[A][B][C][2]) + vc[0][A]+max(B-b, 0)+max(C-c, 0)-(A+B+C+1));
                                }
                                if (B < (int)vc[1].size()) {
                                        int a = vt[1][B].F;
                                        int c = vt[1][B].S;
                                        dp[A][B+1][C][1] = min(dp[A][B+1][C][1], min(dp[A][B][C][0], dp[A][B][C][2]) + vc[1][B]+max(A-a, 0)+max(C-c, 0)-(A+B+C+1));
                                }
                                if (C < (int)vc[2].size()) {
                                        int a = vt[2][C].F;
                                        int b = vt[2][C].S;
                                        dp[A][B][C+1][2] = min(dp[A][B][C+1][2], min(dp[A][B][C][0], dp[A][B][C][1]) + vc[2][C]+max(A-a,0)+max(B-b, 0)-(A+B+C+1));
                                }
                        }
                }
        }
        int ans = 1e9;
        ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][0], ans);
        ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][1], ans);
        ans = min(dp[vc[0].size()][vc[1].size()][vc[2].size()][2], ans);
        cout << (ans >= 1e9? -1 : ans) << endl;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        solve();
        return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 780212 KB Output is correct
2 Execution timed out 737 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 780212 KB Output is correct
2 Execution timed out 737 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 780236 KB Output is correct
2 Correct 472 ms 780268 KB Output is correct
3 Correct 459 ms 780308 KB Output is correct
4 Correct 469 ms 780312 KB Output is correct
5 Correct 462 ms 780324 KB Output is correct
6 Correct 463 ms 780236 KB Output is correct
7 Correct 457 ms 780236 KB Output is correct
8 Correct 454 ms 780260 KB Output is correct
9 Correct 468 ms 780312 KB Output is correct
10 Correct 478 ms 780308 KB Output is correct
11 Correct 457 ms 780368 KB Output is correct
12 Correct 292 ms 780280 KB Output is correct
13 Correct 315 ms 780216 KB Output is correct
14 Correct 354 ms 780312 KB Output is correct
15 Correct 475 ms 780308 KB Output is correct
16 Correct 475 ms 780416 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 780212 KB Output is correct
2 Execution timed out 737 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -