Submission #531385

#	Time	Username	Problem	Language	Result	Execution time	Memory
531385		scottchou	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	91 ms	162956 KiB

joi2019_ho_t3

#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';
        return 0;
    }
    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 (stderr)

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:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if(point[i].size() > (n + 1) / 2){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25