oj.uz

답안 #953352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953352 2024-03-25T20:52:32 Z OkYqsJJ Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 4 ms 7776 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> G , R , Y;
int n;
string s; 

int dp[61][61][61][4]; 

int brute(int i , int j , int k , int lst){
    int sz = i + j + k ;
    if (sz == n) return 0;
    if (~dp[i][j][k][lst]) return dp[i][j][k][lst]; 
    int a = 1e8 , b = 1e8 , c = 1e8;
    if (lst != 1 && i < G.size()){
        int x = 0; 
        for (int l = 0 ; l < j ; l++) if (R[l] > G[i]) x++; 
        for (int l = 0 ; l < k ; l++) if (Y[l] > G[i]) x++;
        a = brute(i+1 , j , k , 1) + x ; 
    }
    if (lst != 2 && j < R.size()){
       int x = 0;
       for (int l = 0 ; l < i ; l++) if (G[l] > R[j]) x++;
       for (int l = 0 ; l < k ; l++) if (Y[l] > R[j]) x++; 
       b = brute(i , j+1 , k , 2) + x ;
    }
    if (lst != 3 && k < Y.size()){
        int x = 0;
        for (int l = 0 ; l < i ; l++) if (G[l] > Y[k]) x++;
        for (int l = 0 ; l < j ; l++) if (R[l] > Y[k]) x++; 
        c = brute(i , j , k+1 , 3) + x;
    }
    return dp[i][j][k][lst] = min({a , b , c});
}

void doWork(){
    cin >> n >> s;
    for (int i = 0 ; i < n ; i++){
        if (s[i] == 'G') G.push_back(i);
        else if (s[i] == 'R') R.push_back(i);
        else Y.push_back(i); 
    }
    memset(dp , -1 , sizeof dp);
    int ans =  brute(0 , 0 , 0 , 0);
    cout << (ans == 1e8 ? -1 : ans) ;
}   


signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    doWork(); 
}

Compilation message

joi2019_ho_t3.cpp: In function 'int brute(int, int, int, int)':
joi2019_ho_t3.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (lst != 1 && i < G.size()){
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (lst != 2 && j < R.size()){
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (lst != 3 && k < Y.size()){
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 ms 3788 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct

Subtask #2
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 ms 3788 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 2 ms 3932 KB Output is correct
19 Correct 2 ms 3932 KB Output is correct
20 Correct 2 ms 3932 KB Output is correct
21 Correct 2 ms 3932 KB Output is correct
22 Correct 2 ms 3932 KB Output is correct
23 Correct 2 ms 3932 KB Output is correct
24 Correct 2 ms 3932 KB Output is correct
25 Correct 1 ms 3932 KB Output is correct
26 Correct 1 ms 3932 KB Output is correct
27 Correct 2 ms 3932 KB Output is correct
28 Correct 2 ms 3932 KB Output is correct
29 Correct 2 ms 3932 KB Output is correct
30 Correct 2 ms 3932 KB Output is correct
31 Correct 2 ms 3928 KB Output is correct
32 Correct 2 ms 3932 KB Output is correct
33 Correct 1 ms 3936 KB Output is correct
34 Correct 2 ms 3932 KB Output is correct
35 Correct 2 ms 3792 KB Output is correct
36 Correct 2 ms 3932 KB Output is correct
37 Correct 2 ms 3932 KB Output is correct
38 Correct 2 ms 3940 KB Output is correct
39 Correct 2 ms 3792 KB Output is correct
40 Correct 1 ms 3936 KB Output is correct
41 Correct 1 ms 3936 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3932 KB Output is correct
2 Runtime error 4 ms 7776 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 1 ms 3932 KB Output is correct
6 Correct 1 ms 3932 KB Output is correct
7 Correct 1 ms 3932 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 3932 KB Output is correct
10 Correct 1 ms 3932 KB Output is correct
11 Correct 1 ms 3932 KB Output is correct
12 Correct 1 ms 3932 KB Output is correct
13 Correct 2 ms 3932 KB Output is correct
14 Correct 1 ms 3932 KB Output is correct
15 Correct 1 ms 3932 KB Output is correct
16 Correct 1 ms 3788 KB Output is correct
17 Correct 1 ms 3932 KB Output is correct
18 Correct 2 ms 3932 KB Output is correct
19 Correct 2 ms 3932 KB Output is correct
20 Correct 2 ms 3932 KB Output is correct
21 Correct 2 ms 3932 KB Output is correct
22 Correct 2 ms 3932 KB Output is correct
23 Correct 2 ms 3932 KB Output is correct
24 Correct 2 ms 3932 KB Output is correct
25 Correct 1 ms 3932 KB Output is correct
26 Correct 1 ms 3932 KB Output is correct
27 Correct 2 ms 3932 KB Output is correct
28 Correct 2 ms 3932 KB Output is correct
29 Correct 2 ms 3932 KB Output is correct
30 Correct 2 ms 3932 KB Output is correct
31 Correct 2 ms 3928 KB Output is correct
32 Correct 2 ms 3932 KB Output is correct
33 Correct 1 ms 3936 KB Output is correct
34 Correct 2 ms 3932 KB Output is correct
35 Correct 2 ms 3792 KB Output is correct
36 Correct 2 ms 3932 KB Output is correct
37 Correct 2 ms 3932 KB Output is correct
38 Correct 2 ms 3940 KB Output is correct
39 Correct 2 ms 3792 KB Output is correct
40 Correct 1 ms 3936 KB Output is correct
41 Correct 1 ms 3936 KB Output is correct
42 Correct 1 ms 3932 KB Output is correct
43 Runtime error 4 ms 7776 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -