oj.uz

Submission #896533

# Submission time Handle Problem Language Result Execution time Memory
896533 2024-01-01T15:55:14 Z Andrey Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 199 ms 754848 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> wut[3];
int dp[400][401][401][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> haha(n);
    for(int i = 0; i < n; i++) {
        if(s[i] == 'R') {
            haha[i] = 0;
        }
        else if(s[i] == 'G') {
            haha[i] = 1;
        }
        else {
            haha[i] = 2;
        }
        wut[haha[i]].push_back(i);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= wut[0].size(); j++) {
            for(int k = 0; k <= wut[1].size(); k++) {
                dp[i][j][k][0] = 1e9;
                dp[i][j][k][1] = 1e9;
                dp[i][j][k][2] = 1e9;
                if(j+k > i+1 || i+1-j-k > wut[2].size()) {
                    continue;
                }
                int b = i+1-j-k;
                if(i > 0) {
                    if(j != 0) {
                        dp[i][j][k][0] = min(dp[i][j][k][0],min(dp[i-1][j-1][k][1],dp[i-1][j-1][k][2])+abs(i-wut[0][j-1]));
                    }
                    if(k != 0) {
                        dp[i][j][k][1] = min(dp[i][j][k][1],min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][2])+abs(i-wut[1][k-1]));
                    }
                    if(b != 0) {
                        dp[i][j][k][2] = min(dp[i][j][k][2],min(dp[i-1][j][k][0],dp[i-1][j][k][1])+abs(i-wut[2][b-1]));
                    }
                }
                else {
                    if(j > 0) {
                        dp[i][j][k][0] = abs(i-wut[0][0]);
                    }
                    if(k > 0) {
                        dp[i][j][k][1] = abs(i-wut[1][0]);
                    }
                    if(b > 0) {
                        dp[i][j][k][2] = abs(i-wut[2][0]);
                    }
                }
            }
        }
    }
    int ans = dp[n-1][wut[0].size()][wut[1].size()][0];
    ans = min(ans,dp[n-1][wut[0].size()][wut[1].size()][1]);
    ans = min(ans,dp[n-1][wut[0].size()][wut[1].size()][2]);
    if(ans >= (int)1e9) {
        cout << -1;
    }
    else {
        cout << ans/2;
    }
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int j = 0; j <= wut[0].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             for(int k = 0; k <= wut[1].size(); k++) {
      |                            ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                 if(j+k > i+1 || i+1-j-k > wut[2].size()) {
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4560 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 3 ms 27144 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Incorrect 3 ms 26972 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4560 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 3 ms 27144 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Incorrect 3 ms 26972 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 1 ms 4444 KB Output is correct
2 Correct 199 ms 754488 KB Output is correct
3 Correct 98 ms 753624 KB Output is correct
4 Correct 97 ms 754824 KB Output is correct
5 Correct 92 ms 754516 KB Output is correct
6 Correct 95 ms 754540 KB Output is correct
7 Correct 99 ms 753488 KB Output is correct
8 Correct 100 ms 753496 KB Output is correct
9 Correct 100 ms 751652 KB Output is correct
10 Correct 97 ms 754848 KB Output is correct
11 Correct 98 ms 754512 KB Output is correct
12 Correct 41 ms 388436 KB Output is correct
13 Correct 58 ms 517804 KB Output is correct
14 Correct 73 ms 624208 KB Output is correct
15 Correct 92 ms 754420 KB Output is correct
16 Correct 98 ms 754516 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 4560 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 4 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 3 ms 26972 KB Output is correct
8 Correct 3 ms 27144 KB Output is correct
9 Correct 4 ms 26972 KB Output is correct
10 Correct 3 ms 26972 KB Output is correct
11 Incorrect 3 ms 26972 KB Output isn't correct
12 Halted 0 ms 0 KB -