oj.uz

Submission #116446

# Submission time Handle Problem Language Result Execution time Memory
116446 2019-06-12T13:13:10 Z 송준혁(#2869, songc) Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
20 / 100
 500 ms 258496 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N;
char str[440];
vector<int> R, G, Y;
int D[4][404][404][404];

int f(int l, int r, int g, int y){
    if (r+g+y >= N) return 0;
    if (D[l][r][g][y] != INF) return D[l][r][g][y];
    if (l != 0 && r < (int)R.size()){
        int ret = f(0, r+1, g, y);
        ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), R[r]) - G.begin()));
        ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), R[r]) - Y.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    if (l != 1 && g < (int)G.size()){
        int ret = f(1, r, g+1, y);
        ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), G[g]) - R.begin()));
        ret += max(0, y - (int)(lower_bound(Y.begin(), Y.end(), G[g]) - Y.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    if (l != 2 && y < (int)Y.size()){
        int ret = f(2, r, g, y+1);
        ret += max(0, r - (int)(lower_bound(R.begin(), R.end(), Y[y]) - R.begin()));
        ret += max(0, g - (int)(lower_bound(G.begin(), G.end(), Y[y]) - G.begin()));
        D[l][r][g][y] = min(D[l][r][g][y], ret);
    }
    return D[l][r][g][y];
}

int main(){
    scanf("%d", &N);
    scanf("%s", str+1);
    for (int i=1; i<=N; i++){
        if (str[i] == 'R') R.push_back(i);
        else if (str[i] == 'G') G.push_back(i);
        else Y.push_back(i);
    }
    for (int i=0; i<4; i++){
        for (int j=0; j<=(int)R.size(); j++){
            for (int k=0; k<=(int)G.size(); k++){
                for (int l=0; l<=(int)Y.size(); l++){
                    D[i][j][k][l] = INF;
                }
            }
        }
    }
    int ans = f(3, 0, 0, 0);
    if (ans == INF) puts("-1");
    else printf("%d\n", ans);
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", str+1);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
5.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 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 384 KB Output is correct

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 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Execution timed out 1055 ms 3584 KB Time limit exceeded
19 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 167 ms 258272 KB Output is correct
3 Correct 167 ms 257060 KB Output is correct
4 Correct 170 ms 258496 KB Output is correct
5 Correct 182 ms 258296 KB Output is correct
6 Correct 166 ms 258364 KB Output is correct
7 Correct 168 ms 257016 KB Output is correct
8 Correct 166 ms 256992 KB Output is correct
9 Correct 165 ms 255836 KB Output is correct
10 Correct 170 ms 258356 KB Output is correct
11 Correct 176 ms 258296 KB Output is correct
12 Correct 52 ms 70264 KB Output is correct
13 Correct 86 ms 122616 KB Output is correct
14 Correct 122 ms 176760 KB Output is correct
15 Correct 174 ms 258300 KB Output is correct
16 Correct 174 ms 258424 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 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 640 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 2 ms 896 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 640 KB Output is correct
15 Correct 2 ms 512 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Execution timed out 1055 ms 3584 KB Time limit exceeded
19 Halted 0 ms 0 KB -