Submission #125884

#	Time	Username	Problem	Language	Result	Execution time	Memory
125884		EntityIT	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	138 ms	33912 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

using namespace std;

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

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

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("test.INP", "r", stdin);
    id['R'] = 0;
    id['G'] = 1;
    id['Y'] = 2;

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> 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;

    for (int _ = 0; _ < 3; ++_) f[_].assign(nmbr[0] + 5, vector< vector<int> >(nmbr[1] + 5, vector<int>(nmbr[2] + 5, -1) ) );
    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 <= nmbr[0]; ++i) {
            for (int j = 0; i + j <= ijk && j <= nmbr[1]; ++j) {
                int k = ijk - i - j;
                if (k > nmbr[2]) continue; 

                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] ]);


    cout << ans;

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:24:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         ++nmbr[ id[ c[i] ] ];
                          ^
joi2019_ho_t3.cpp:31:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         ++cnt[ id[ c[i] ] ][i];
                         ^
joi2019_ho_t3.cpp:34: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:34: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;
                                                                    ^

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