oj.uz

Submission #768138

# Submission time Handle Problem Language Result Execution time Memory
768138 2023-06-27T14:15:01 Z 1bin Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 757520 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
int n, dp[401][401][401][3], sz[3], cnt[401][3];
vector<int> v[3];
string s, t = "RGY";

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> s;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++)
            if(s[i] == t[j]) v[j].emplace_back(i);
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i < 3; i++) sz[i] = v[i].size();
    for(int i = 0; i < 3; i++) if(s[0] == t[i]) cnt[0][i] = 1;
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 3; j++) cnt[i][j] = cnt[i - 1][j] + (s[i] == t[j]);
    }
    
    for(int i = 0; i < 3; i++) dp[0][0][0][i] = 0;
    for(int i = 0; i <= sz[0]; i++)
        for(int j = 0; j <= sz[1]; j++)
            for(int k = 0; k <= sz[2]; k++)
                if(i + j + k){
                    if(i) dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + max(j - cnt[v[0][i - 1]][1], 0) + max(k - cnt[v[0][i - 1]][2], 0);
                    if(j) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + max(i - cnt[v[1][j - 1]][0], 0) + max(k - cnt[v[1][j - 1]][2], 0);
                    if(k) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + max(i - cnt[v[2][k - 1]][0], 0) + max(j - cnt[v[2][k - 1]][1], 0);
                }
    int ans = 1e9;
    for(int i = 0; i < 3; i++) ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
    if(ans == 1e9) cout << -1;
    else cout << ans;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 614 ms 757424 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 614 ms 757424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 757400 KB Output is correct
2 Correct 248 ms 757384 KB Output is correct
3 Correct 246 ms 757344 KB Output is correct
4 Correct 248 ms 757320 KB Output is correct
5 Correct 251 ms 757308 KB Output is correct
6 Correct 250 ms 757420 KB Output is correct
7 Correct 264 ms 757368 KB Output is correct
8 Correct 253 ms 757488 KB Output is correct
9 Correct 250 ms 757400 KB Output is correct
10 Correct 254 ms 757380 KB Output is correct
11 Correct 252 ms 757348 KB Output is correct
12 Correct 281 ms 757336 KB Output is correct
13 Correct 251 ms 757340 KB Output is correct
14 Correct 255 ms 757520 KB Output is correct
15 Correct 257 ms 757380 KB Output is correct
16 Correct 249 ms 757352 KB Output is correct

Subtask #4
0 / 25.0

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