oj.uz

Submission #98274

# Submission time Handle Problem Language Result Execution time Memory
98274 2019-02-21T18:39:43 Z someone_aa Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 143 ms 164984 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];
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 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;

                        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] + abs(v[0][c0] - (c0+c1+c2+1)));
                        }
                        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] + abs(v[1][c1] - (c0+c1+c2+1)));
                        }
                        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] + abs(v[2][c2] - (c0+c1+c2+1)));
                        }
                    }
                }
            }
        }
    }

    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/2)<<"\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:25: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:26: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:27: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:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int c0=0;c0<=v[0].size();c0++) {
                  ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int c1=0;c1<=v[1].size();c1++) {
                      ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int c2=0;c2<=v[2].size();c2++) {
                          ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(nxt == 0 && c0 < v[0].size()) {
                                        ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         else if(nxt == 1 && c1 < v[1].size()) {
                                             ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:51: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 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 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 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 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 3 ms 384 KB Output is correct
2 Correct 123 ms 164928 KB Output is correct
3 Correct 125 ms 164176 KB Output is correct
4 Correct 126 ms 164956 KB Output is correct
5 Correct 124 ms 164984 KB Output is correct
6 Correct 124 ms 164956 KB Output is correct
7 Correct 120 ms 164132 KB Output is correct
8 Correct 120 ms 164260 KB Output is correct
9 Correct 128 ms 163320 KB Output is correct
10 Correct 124 ms 164984 KB Output is correct
11 Correct 130 ms 164916 KB Output is correct
12 Correct 41 ms 44920 KB Output is correct
13 Correct 71 ms 78456 KB Output is correct
14 Correct 82 ms 112888 KB Output is correct
15 Correct 117 ms 164900 KB Output is correct
16 Correct 143 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 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 3 ms 640 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 -