oj.uz

Submission #647673

# Submission time Handle Problem Language Result Execution time Memory
647673 2022-10-03T14:43:41 Z Ronin13 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 445 ms 757460 KB 
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

int pref[401][3];
int dp[401][401][401][3];

vector <int> vec[3];

int main(){
    int n; cin >> n;
    char c[n + 1];
    for(int i = 1; i <= n;i ++) cin >> c[i];
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < 3; j++) pref[i][j] = pref[i - 1][j];
        if(c[i] == 'R')
            pref[i][0]++, vec[0].pb(i);
        if(c[i] == 'G')
            pref[i][1]++, vec[1].pb(i);
        if(c[i] == 'Y')
            pref[i][2]++, vec[2].pb(i);
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            for(int x= 0; x <= n; x++){
                for(int k = 0; k < 3; k++){
                    dp[i][j][x][k] = 1e9;
                }
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for(int i = 0; i <= (int)vec[0].size(); i++){
        for(int j = 0; j <= (int)vec[1].size(); j++){
            for(int k = 0; k <= (int)vec[2].size(); k++){
                if(i){
                    int x = vec[0][i - 1];
                    int v = max(pref[x][1] - j, 0);
                    int u = max(pref[x][2] - k, 0);
                    dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + u + v;
                }
                if(j){
                    int x = vec[1][j - 1];
                    int v = max(pref[x][0] - i, 0);
                    int u = max(pref[x][2] - k, 0);
                    dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + u + v;
                }
                if(k){
                    int x = vec[2][k - 1];
                    int v = max(pref[x][0] - i, 0);
                    int u = max(pref[x][1] - j, 0);
                    dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + u + v;
                }
            }
        }
    }
    int l1 = vec[0].size();
    int l2 = vec[1].size();
    int l3 = vec[2].size();
    int x =  min({dp[l1][l2][l3][0], dp[l1][l2][l3][1], dp[l1][l2][l3][2]});
    if(x == 1e9){
        cout << -1 << "\n";
    }
    else cout << x;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1328 KB Output is correct
8 Correct 1 ms 1328 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Incorrect 1 ms 1364 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1328 KB Output is correct
8 Correct 1 ms 1328 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Incorrect 1 ms 1364 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 445 ms 757316 KB Output is correct
3 Correct 371 ms 755240 KB Output is correct
4 Correct 368 ms 757452 KB Output is correct
5 Correct 377 ms 757380 KB Output is correct
6 Correct 350 ms 757312 KB Output is correct
7 Correct 354 ms 755116 KB Output is correct
8 Correct 370 ms 755164 KB Output is correct
9 Correct 348 ms 751416 KB Output is correct
10 Correct 337 ms 757324 KB Output is correct
11 Correct 413 ms 757380 KB Output is correct
12 Correct 96 ms 202672 KB Output is correct
13 Correct 159 ms 357396 KB Output is correct
14 Correct 253 ms 517336 KB Output is correct
15 Correct 361 ms 757324 KB Output is correct
16 Correct 338 ms 757460 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 1328 KB Output is correct
8 Correct 1 ms 1328 KB Output is correct
9 Correct 1 ms 1364 KB Output is correct
10 Correct 1 ms 1364 KB Output is correct
11 Correct 1 ms 1364 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Incorrect 1 ms 1364 KB Output isn't correct
14 Halted 0 ms 0 KB -