oj.uz

답안 #538547

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538547 2022-03-17T04:37:51 Z 79brue Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 104 ms 4084 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[402];
int DP[2][402][402][3];
int cnt[3];
vector<int> occ[3];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        char c;
        scanf(" %c", &c);
        arr[i] = c=='R' ? 0 : c=='G' ? 1 : 2;
        cnt[arr[i]]++;
        occ[arr[i]].push_back(i);
    }

    for(int i=0; i<2; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) for(int l=0; l<3; l++) DP[i][j][k][l]=1e9;
    DP[0][0][0][0] = DP[0][0][0][1] = DP[0][0][0][2] = 0;

    for(int i=1; i<=n; i++){
        int ri = i%2;
        for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) for(int l=0; l<3; l++) DP[ri][j][k][l]=1e9;

        for(int j=0; j<i && j<=cnt[0]; j++){
            for(int k=0; j+k<i && k<=cnt[1]; k++){
                int l = i-j-k-1;
                if(l>cnt[2]) continue;
                for(int d=0; d<3; d++){
                    if(j<cnt[0] && d!=0) DP[ri][j+1][k][0] = min(DP[ri][j+1][k][0], DP[!ri][j][k][d] + abs(i-occ[0][j]));
                    if(k<cnt[1] && d!=1) DP[ri][j][k+1][1] = min(DP[ri][j][k+1][1], DP[!ri][j][k][d] + abs(i-occ[1][k]));
                    if(l<cnt[2] && d!=2) DP[ri][j][k][2] = min(DP[ri][j][k][2], DP[!ri][j][k][d] + abs(i-occ[2][l]));
                }
            }
        }
    }

    int ans = 1e9;
    for(int i=0; i<3; i++) ans = min(ans, DP[n%2][cnt[0]][cnt[1]][i]);
    printf("%d", ans==1000000000 ? -1 : ans/2);
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf(" %c", &c);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 83 ms 4080 KB Output is correct
3 Correct 100 ms 4072 KB Output is correct
4 Correct 100 ms 4020 KB Output is correct
5 Correct 80 ms 4084 KB Output is correct
6 Correct 104 ms 4032 KB Output is correct
7 Correct 87 ms 4076 KB Output is correct
8 Correct 92 ms 4080 KB Output is correct
9 Correct 85 ms 4060 KB Output is correct
10 Correct 86 ms 4084 KB Output is correct
11 Correct 92 ms 4052 KB Output is correct
12 Correct 14 ms 2272 KB Output is correct
13 Correct 28 ms 2900 KB Output is correct
14 Correct 49 ms 3412 KB Output is correct
15 Correct 86 ms 4084 KB Output is correct
16 Correct 92 ms 4084 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 628 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 440 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 440 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -