oj.uz

Submission #531507

# Submission time Handle Problem Language Result Execution time Memory
531507 2022-03-01T00:31:08 Z scottchou Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 61 ms 162952 KB 
#include<iostream>
#include<cassert>
#include<vector>
using namespace std;
int const N = 405;
int a[N], n;
int const R = 0, G = 1, Y = 2, inf = 1e9;
vector<int> point[3];
int dp[N][N][N][3], backp[3][N];
void solve(){
    dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0;
    for(int i = 0; i <= point[0].size(); i++){
        for(int j = 0; j <= point[1].size(); j++){
            for(int k = 0;  k <= point[2].size(); k++){
                if(!i && !j && !k)
                    continue;
                for(int t = 0; t < 3; t++){
                    int backcnt = 0;
                    if((t == 0 && !i) || (t == 1 && !j) || (t == 2 && !k)){
                        dp[i][j][k][t] = inf;
                        continue;
                    }
                    if(t == 0){
                        if(j)
                            backcnt += max(j - backp[1][point[t][i - 1]], 0);
                        if(k)
                            backcnt += max(k - backp[2][point[t][i - 1]], 0);
                        dp[i][j][k][t] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(point[0][i - 1] + backcnt - (i + j + k - 1));
                    }else if(t == 1){
                        if(i)
                            backcnt += max(i - backp[0][point[t][j - 1]], 0);
                        if(k)
                            backcnt += max(k - backp[2][point[t][j - 1]], 0);
                        dp[i][j][k][t] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(point[1][j - 1] + backcnt - (i + j + k - 1));
                    }else if(t == 2){
                        if(i)
                            backcnt += max(i - backp[0][point[t][k - 1]], 0);
                        if(j)
                            backcnt += max(j - backp[1][point[t][k - 1]], 0);
                        dp[i][j][k][t] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + abs(point[2][k - 1] + backcnt - (i + j + k - 1));
                    }
                }
            }
        }
    }
    cout << min(dp[point[0].size()][point[1].size()][point[2].size()][0],min(dp[point[0].size()][point[1].size()][point[2].size()][1], dp[point[0].size()][point[1].size()][point[2].size()][2])) << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    char in;
    if(n == 1){
        cout <<  0 << '\n';
    }
    for(int i = 0; i < n; i++){
        cin >> in;
        if(in == 'R'){
            a[i] = 0;
        }else if(in == 'G')
            a[i] = 1;
        else{
            a[i] = 2;
        }
        point[a[i]].push_back(i);
    }
    for(int i = 0; i < 3; i++){
        if(point[i].size() > (n + 1) / 2){
            cout << -1 << '\n';
            return 0;
        }
        backp[i][n] = point[i].size();
        int p = point[i].size() - 1;
        for(int j = n - 1; j >= 0; j--){
            if(p >= 0 && point[i][p] == j){
                backp[i][j] = p;
                p--;
            }else{
                backp[i][j] = backp[i][j + 1];
            }
        }
    }
    solve();
}

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i <= point[0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:13:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for(int j = 0; j <= point[1].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:14:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |             for(int k = 0;  k <= point[2].size(); k++){
      |                             ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:68:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |         if(point[i].size() > (n + 1) / 2){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 61 ms 162864 KB Output is correct
3 Correct 55 ms 162092 KB Output is correct
4 Correct 59 ms 162884 KB Output is correct
5 Correct 58 ms 162872 KB Output is correct
6 Correct 57 ms 162896 KB Output is correct
7 Correct 59 ms 162088 KB Output is correct
8 Correct 57 ms 162104 KB Output is correct
9 Correct 56 ms 161348 KB Output is correct
10 Correct 57 ms 162952 KB Output is correct
11 Correct 58 ms 162880 KB Output is correct
12 Correct 17 ms 43980 KB Output is correct
13 Correct 28 ms 77056 KB Output is correct
14 Correct 39 ms 111300 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -