oj.uz

Submission #98286

# Submission time Handle Problem Language Result Execution time Memory
98286 2019-02-21T21:43:38 Z someone_aa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 141 ms 165008 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 410;
const int inf = 100000000;
int dp[maxn][maxn][maxn][3];
int n, arr[maxn], pref[maxn][3];
string code;

vector<int>v[3];

int main() {
    cin>>n;
    cin>>code;

    for(int i=0;i<code.length();i++) {
        if(code[i] == 'R') arr[i + 1] = 0;
        else if(code[i] == 'G') arr[i + 1] = 1;
        else arr[i + 1] = 2;
        v[arr[i+1]].pb(i + 1);

        for(int j=0;j<=2;j++) {
            pref[i+1][j] = pref[i][j];
        }
        pref[i+1][arr[i+1]]++;
    }

    for(int i=0;i<=v[0].size()+1;i++) {
        for(int j=0;j<=v[1].size()+1;j++) {
            for(int k=0;k<=v[2].size()+1;k++) {
                for(int l=0;l<=2;l++) {
                    dp[i][j][k][l] = inf;
                }
            }
        }
    }

    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

    for(int c0=0;c0<=v[0].size();c0++) {
        for(int c1=0;c1<=v[1].size();c1++) {
            for(int c2=0;c2<=v[2].size();c2++) {
                for(int last=0;last<=2;last++) {
                    if(dp[c0][c1][c2][last] == inf) continue;
                    for(int nxt=0;nxt<=2;nxt++) {
                        if(last == nxt) continue;

                        int ind = c0 + c1 + c2 + 1;
                        int c[3] = {c0, c1, c2};
                        int cost = 0;
                        c[nxt]++;
                        for(int i=0;i<=2;i++) {
                            cost += max(0, pref[ind][i] - c[i]);
                        }
                        c[nxt]--;

                        if(nxt == 0 && c0 < v[0].size()) {
                            dp[c0+1][c1][c2][0] = min(dp[c0+1][c1][c2][0], dp[c0][c1][c2][last] + cost);
                        }
                        else if(nxt == 1 && c1 < v[1].size()) {
                            dp[c0][c1+1][c2][1] = min(dp[c0][c1+1][c2][1], dp[c0][c1][c2][last] + cost);
                        }
                        else if(nxt == 2 && c2 < v[2].size()) {
                            dp[c0][c1][c2+1][2] = min(dp[c0][c1][c2+1][2], dp[c0][c1][c2][last] + cost);
                        }

                    }
                }
            }
        }
    }

    int result = min(min(dp[v[0].size()][v[1].size()][v[2].size()][0], dp[v[0].size()][v[1].size()][v[2].size()][1]), dp[v[0].size()][v[1].size()][v[2].size()][2]);

    if(result == inf) {
        cout<<"-1\n";
        return 0;
    }

    cout<<result<<"\n";
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<code.length();i++) {
                 ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<=v[0].size()+1;i++) {
                 ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<=v[1].size()+1;j++) {
                     ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k=0;k<=v[2].size()+1;k++) {
                         ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int c0=0;c0<=v[0].size();c0++) {
                  ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int c1=0;c1<=v[1].size();c1++) {
                      ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int c2=0;c2<=v[2].size();c2++) {
                          ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:59:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(nxt == 0 && c0 < v[0].size()) {
                                        ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:62:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         else if(nxt == 1 && c1 < v[1].size()) {
                                             ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:65:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         else if(nxt == 2 && c2 < v[2].size()) {
                                             ~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Incorrect 2 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Incorrect 2 ms 640 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 2 ms 384 KB Output is correct
2 Correct 131 ms 164972 KB Output is correct
3 Correct 122 ms 164188 KB Output is correct
4 Correct 141 ms 164984 KB Output is correct
5 Correct 117 ms 164984 KB Output is correct
6 Correct 134 ms 164984 KB Output is correct
7 Correct 122 ms 164112 KB Output is correct
8 Correct 127 ms 164188 KB Output is correct
9 Correct 123 ms 163248 KB Output is correct
10 Correct 126 ms 164984 KB Output is correct
11 Correct 129 ms 164960 KB Output is correct
12 Correct 40 ms 44920 KB Output is correct
13 Correct 73 ms 78456 KB Output is correct
14 Correct 87 ms 112888 KB Output is correct
15 Correct 119 ms 165008 KB Output is correct
16 Correct 137 ms 164984 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Incorrect 2 ms 640 KB Output isn't correct
12 Halted 0 ms 0 KB -