제출 #512603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
512603		Jarif_Rahman	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	485 ms	755604 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+5;
int dp[400][401][401][3];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; str ss; cin >> n >> ss;
    vector<int> s;
    for(int i = 0; i < n; i++){
        if(ss[i] == 'R') s.pb(0);
        if(ss[i] == 'G') s.pb(1);
        if(ss[i] == 'Y') s.pb(2);
    }

    vector<vector<int>> cnt(n, vector<int>(3, 0));
    vector<vector<int>> pos(3);
    for(int i = 0; i < n; i++) for(int j = 0; j <= n; j++) for(int k = 0; k <= n; k++)
        for(int c = 0; c < 3; c++) dp[i][j][k][c] = inf;

    for(int i = n-1; i >= 0; i--){
        pos[s[i]].pb(i);
        if(i != n-1) cnt[i][0] = cnt[i+1][0], cnt[i][1] = cnt[i+1][1], cnt[i][2] = cnt[i+1][2];
        cnt[i][s[i]]++;
    }

    vector<vector<int>> o(3);
    for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) if(i != j) o[i].pb(j);

    for(int i = n-1; i >= 0; i--){
        int c[3];
        for(c[0] = 0; c[0] <= min(cnt[0][0], n-i); c[0]++) for(c[1] = 0; c[1] <= cnt[0][1] && c[1]+c[0] <= n-i; c[1]++){
            c[2] = n-i-c[0]-c[1];
            if(c[2] > cnt[0][2]) continue;
            for(int cl = 0; cl < 3; cl++){
                if(c[cl] == 0) continue;
                if(c[cl] > pos[cl].size()) continue;
                for(int j = 0; j < 2; j++){
                    int cur = 0;
                    c[cl]--;
                    if(i != n-1) cur+=dp[i+1][c[0]][c[1]][o[cl][j]];
                    c[cl]++;
                    if(i == n-1) cur+=abs(pos[cl][c[cl]-1]-i);
                    else cur+=abs(pos[cl][c[cl]-1]-max(0, c[o[cl][0]]-cnt[pos[cl][c[cl]-1]][o[cl][0]])
                        -max(0, c[o[cl][1]]-cnt[pos[cl][c[cl]-1]][o[cl][1]])-i);

                    dp[i][c[0]][c[1]][cl] = min(dp[i][c[0]][c[1]][cl], cur);
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int c = 0; c < 3; c++)
        ans = min(ans, dp[0][i][j][c]);
    if(ans >= inf) ans = -1;
    cout << ans << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 if(c[cl] > pos[cl].size()) continue;
      |                    ~~~~~~^~~~~~~~~~~~~~~~

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