oj.uz

Submission #716379

# Submission time Handle Problem Language Result Execution time Memory
716379 2023-03-29T21:52:30 Z Kahou Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 478 ms 780500 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];

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);
        }
        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 < vc[0].size()) dp[A+1][B][C][0] = min(dp[A+1][B][C][0], min(dp[A][B][C][1], dp[A][B][C][2]) + max(vc[0][A], A+B+C+1)-(A+B+C+1));
                                if (B < vc[1].size()) dp[A][B+1][C][1] = min(dp[A][B+1][C][1], min(dp[A][B][C][0], dp[A][B][C][2]) + max(vc[1][B], A+B+C+1)-(A+B+C+1));
                                if (C < vc[2].size()) dp[A][B][C+1][2] = min(dp[A][B][C+1][2], min(dp[A][B][C][0], dp[A][B][C][1]) + max(vc[2][C], A+B+C+1)-(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;
}

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:31:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |                                 if (A < vc[0].size()) dp[A+1][B][C][0] = min(dp[A+1][B][C][0], min(dp[A][B][C][1], dp[A][B][C][2]) + max(vc[0][A], A+B+C+1)-(A+B+C+1));
      |                                     ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |                                 if (B < vc[1].size()) dp[A][B+1][C][1] = min(dp[A][B+1][C][1], min(dp[A][B][C][0], dp[A][B][C][2]) + max(vc[1][B], A+B+C+1)-(A+B+C+1));
      |                                     ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:33:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |                                 if (C < vc[2].size()) dp[A][B][C+1][2] = min(dp[A][B][C+1][2], min(dp[A][B][C][0], dp[A][B][C][1]) + max(vc[2][C], A+B+C+1)-(A+B+C+1));
      |                                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 780188 KB Output is correct
2 Correct 283 ms 780240 KB Output is correct
3 Correct 294 ms 780272 KB Output is correct
4 Correct 274 ms 780244 KB Output is correct
5 Correct 281 ms 780296 KB Output is correct
6 Correct 286 ms 780192 KB Output is correct
7 Correct 280 ms 780268 KB Output is correct
8 Correct 308 ms 780212 KB Output is correct
9 Correct 291 ms 780248 KB Output is correct
10 Correct 278 ms 780376 KB Output is correct
11 Incorrect 281 ms 780240 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 780188 KB Output is correct
2 Correct 283 ms 780240 KB Output is correct
3 Correct 294 ms 780272 KB Output is correct
4 Correct 274 ms 780244 KB Output is correct
5 Correct 281 ms 780296 KB Output is correct
6 Correct 286 ms 780192 KB Output is correct
7 Correct 280 ms 780268 KB Output is correct
8 Correct 308 ms 780212 KB Output is correct
9 Correct 291 ms 780248 KB Output is correct
10 Correct 278 ms 780376 KB Output is correct
11 Incorrect 281 ms 780240 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 280 ms 780196 KB Output is correct
2 Correct 467 ms 780312 KB Output is correct
3 Correct 456 ms 780500 KB Output is correct
4 Correct 450 ms 780364 KB Output is correct
5 Correct 463 ms 780348 KB Output is correct
6 Correct 465 ms 780324 KB Output is correct
7 Correct 425 ms 780308 KB Output is correct
8 Correct 465 ms 780196 KB Output is correct
9 Correct 428 ms 780260 KB Output is correct
10 Correct 451 ms 780312 KB Output is correct
11 Correct 475 ms 780308 KB Output is correct
12 Correct 291 ms 780436 KB Output is correct
13 Correct 327 ms 780372 KB Output is correct
14 Correct 361 ms 780432 KB Output is correct
15 Correct 478 ms 780208 KB Output is correct
16 Correct 449 ms 780300 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 780188 KB Output is correct
2 Correct 283 ms 780240 KB Output is correct
3 Correct 294 ms 780272 KB Output is correct
4 Correct 274 ms 780244 KB Output is correct
5 Correct 281 ms 780296 KB Output is correct
6 Correct 286 ms 780192 KB Output is correct
7 Correct 280 ms 780268 KB Output is correct
8 Correct 308 ms 780212 KB Output is correct
9 Correct 291 ms 780248 KB Output is correct
10 Correct 278 ms 780376 KB Output is correct
11 Incorrect 281 ms 780240 KB Output isn't correct
12 Halted 0 ms 0 KB -