oj.uz

Submission #125878

# Submission time Handle Problem Language Result Execution time Memory
125878 2019-07-06T13:29:23 Z EntityIT Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 780652 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 405;
int n, id[200], cnt[3][N], pos[3][N], iC[3], f[3][N][N][N], nmbr[3];
char c[N];

void update (int &_a, int _b) {
    if (_a == -1 || _a > _b) _a = _b;
}

int main () {
    freopen("test.INP", "r", stdin);
    id['R'] = 0;
    id['G'] = 1;
    id['Y'] = 2;

    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%c", c + i);
        ++nmbr[ id[ c[i] ] ];
    }

    for (int i = 1; i <= n; ++i) {
        cnt[0][i] = cnt[0][i - 1];
        cnt[1][i] = cnt[1][i - 1];
        cnt[2][i] = cnt[2][i - 1];
        ++cnt[ id[ c[i] ] ][i];
    }

    for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;

    memset(f, -1, sizeof f);
    f[0][0][0][0] = f[1][0][0][0] = f[2][0][0][0] = 0;

    for (int ijk = 0; ijk <= n; ++ijk) {
        for (int i = 0; i <= ijk; ++i) {
            for (int j = 0; i + j <= ijk; ++j) {
                int k = ijk - i - j;

                if (f[0][i][j][k] != -1) {
                    if (j < nmbr[1]) update (f[1][i][j + 1][k], f[0][i][j][k] + max(0, cnt[0][ pos[1][j + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[2][ pos[1][j + 1] ] - cnt[2][ pos[2][k] ]) );
                    if (k < nmbr[2]) update (f[2][i][j][k + 1], f[0][i][j][k] + max(0, cnt[0][ pos[2][k + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[1][ pos[2][k + 1] ] - cnt[1][ pos[1][j] ]) );
                }
                if (f[1][i][j][k] != -1) {
                    if (i < nmbr[0]) update (f[0][i + 1][j][k], f[1][i][j][k] + max(0, cnt[1][ pos[0][i + 1] ] - cnt[1][ pos[1][j] ]) + max(0, cnt[2][ pos[0][i + 1] ] - cnt[2][ pos[2][k] ]) );
                    if (k < nmbr[2]) update (f[2][i][j][k + 1], f[1][i][j][k] + max(0, cnt[0][ pos[2][k + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[1][ pos[2][k + 1] ] - cnt[1][ pos[1][j] ]) );
                }
                if (f[2][i][j][k] != -1) {
                    if (i < nmbr[0]) update (f[0][i + 1][j][k], f[2][i][j][k] + max(0, cnt[1][ pos[0][i + 1] ] - cnt[1][ pos[1][j] ]) + max(0, cnt[2][ pos[0][i + 1] ] - cnt[2][ pos[2][k] ]) );
                    if (j < nmbr[1]) update (f[1][i][j + 1][k], f[2][i][j][k] + max(0, cnt[0][ pos[1][j + 1] ] - cnt[0][ pos[0][i] ]) + max(0, cnt[2][ pos[1][j + 1] ] - cnt[2][ pos[2][k] ]) );
                }
            }
        }
    }

    int ans = -1;
    if (f[0][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[0][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);
    if (f[1][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[1][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);
    if (f[2][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ] != -1) update(ans, f[2][ nmbr[0] ][ nmbr[1] ][ nmbr[2] ]);


    printf("%d", ans);

    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         ++nmbr[ id[ c[i] ] ];
                          ^
joi2019_ho_t3.cpp:29:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         ++cnt[ id[ c[i] ] ][i];
                         ^
joi2019_ho_t3.cpp:32:48: warning: array subscript has type 'char' [-Wchar-subscripts]
     for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;
                                                ^
joi2019_ho_t3.cpp:32:68: warning: array subscript has type 'char' [-Wchar-subscripts]
     for (int i = 1; i <= n; ++i) pos[ id[ c[i] ] ][ ++iC[ id[ c[i] ] ] ] = i;
                                                                    ^
joi2019_ho_t3.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("test.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n", &n);
     ~~~~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", c + i);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 635 ms 780652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 635 ms 780652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 639 ms 780392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 635 ms 780652 KB Time limit exceeded
2 Halted 0 ms 0 KB -