oj.uz

답안 #531505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531505 2022-03-01T00:30:12 Z scottchou Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 68 ms 162952 KB 
#include<iostream>
#include<cassert>
#include<vector>
using namespace std;
int const N = 405;
int a[N], n;
int const R = 0, G = 1, Y = 2, inf = 1e9;
vector<int> point[3];
int dp[N][N][N][3], backp[3][N];
void solve(){
    dp[0][0][0][0] = 0; dp[0][0][0][1] = 0; dp[0][0][0][2] = 0;
    for(int i = 0; i <= point[0].size(); i++){
        for(int j = 0; j <= point[1].size(); j++){
            for(int k = 0;  k <= point[2].size(); k++){
                if(!i && !j && !k)
                    continue;
                for(int t = 0; t < 3; t++){
                    int backcnt = 0;
                    if((t == 0 && !i) || (t == 1 && !j) || (t == 2 && !k)){
                        dp[i][j][k][t] = inf;
                        continue;
                    }
                    if(t == 0){
                        if(j)
                            backcnt += max(j - backp[1][point[t][i - 1]], 0);
                        if(k)
                            backcnt += max(k - backp[2][point[t][i - 1]], 0);
                        dp[i][j][k][t] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + abs(point[0][i - 1] - (i + j + k - 1));
                    }else if(t == 1){
                        if(i)
                            backcnt += max(i - backp[0][point[t][j - 1]], 0);
                        if(k)
                            backcnt += max(k - backp[2][point[t][j - 1]], 0);
                        dp[i][j][k][t] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + abs(point[1][j - 1] - (i + j + k - 1));
                    }else if(t == 2){
                        if(i)
                            backcnt += max(i - backp[0][point[t][k - 1]], 0);
                        if(j)
                            backcnt += max(j - backp[1][point[t][k - 1]], 0);
                        dp[i][j][k][t] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + abs(point[2][k - 1] - (i + j + k - 1));
                    }
                }
            }
        }
    }
    cout << min(dp[point[0].size()][point[1].size()][point[2].size()][0],min(dp[point[0].size()][point[1].size()][point[2].size()][1], dp[point[0].size()][point[1].size()][point[2].size()][2])) / 2 << '\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    char in;
    if(n == 1){
        cout << 0 << '\n';
        return 0;
    }
    for(int i = 0; i < n; i++){
        cin >> in;
        if(in == 'R'){
            a[i] = 0;
        }else if(in == 'G')
            a[i] = 1;
        else{
            a[i] = 2;
        }
        point[a[i]].push_back(i);
    }
    for(int i = 0; i < 3; i++){
        if(point[i].size() > (n + 1) / 2){
            cout << -1 << '\n';
            return 0;
        }
        backp[i][n] = point[i].size();
        int p = point[i].size() - 1;
        for(int j = n - 1; j >= 0; j--){
            if(p >= 0 && point[i][p] == j){
                backp[i][j] = p;
                p--;
            }else{
                backp[i][j] = backp[i][j + 1];
            }
        }
    }
    solve();
}

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0; i <= point[0].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:13:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         for(int j = 0; j <= point[1].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:14:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |             for(int k = 0;  k <= point[2].size(); k++){
      |                             ~~^~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |         if(point[i].size() > (n + 1) / 2){
      |            ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 432 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 432 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 58 ms 162872 KB Output is correct
3 Correct 58 ms 162116 KB Output is correct
4 Correct 58 ms 162884 KB Output is correct
5 Correct 57 ms 162940 KB Output is correct
6 Correct 56 ms 162880 KB Output is correct
7 Correct 57 ms 162116 KB Output is correct
8 Correct 62 ms 162228 KB Output is correct
9 Correct 68 ms 161308 KB Output is correct
10 Correct 60 ms 162884 KB Output is correct
11 Correct 58 ms 162952 KB Output is correct
12 Correct 18 ms 43980 KB Output is correct
13 Correct 30 ms 77060 KB Output is correct
14 Correct 49 ms 111312 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Incorrect 1 ms 432 KB Output isn't correct
12 Halted 0 ms 0 KB -