제출 #368113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
368113		vaaven	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	290 ms	192748 KiB

joi2019_ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
// #define int long  long
    
using namespace std;
    
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
    
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
    
    
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("a.in", "r", stdin);
//    freopen("outputik.txt", "w", stdout);
}

int dp[401][202][202][3];
array<int, 3> cnt[401];
vi kek[3];

int get(array<int, 3> lol, int a, int b, int c){
    int ans = 0;
    ans += max(0, lol[0]-a);
    ans += max(0, lol[1]-b);
    ans += max(0, lol[2]-c);
    return ans;
}

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(auto &i:dp)
        for(auto &j:i)
            for(auto &l:j)
                for(auto &k:l)
                    k = inf;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for(char &c:s){
        if(c == 'R')
            c = 0;
        else if(c == 'G')
            c = 1;
        else
            c = 2;
    }
    for(int i=1; i<=n; i++){
        kek[s[i-1]].pb(i);
    }
    for(int i=1; i<=n; i++){
        cnt[i] = cnt[i-1];
        cnt[i][s[i-1]]++;
    }
    if(max({cnt[n][0], cnt[n][1], cnt[n][2]}) > (n+1)/2){
        cout << -1 << endl;
    }
    for(int i=1; i<=n; i++){
        // cur == R
        {
            for(int r=1; r<=min(i, cnt[n][0]); r++){
                for(int g=0; g<=min(i-1, cnt[n][1]); g++){
                    if(r + g > i)
                        continue;
                    dp[i][r][g][0] = min(dp[i][r][g][0], dp[i-1][r-1][g][1] + get(cnt[kek[0][r-1]], r, g, i-r-g));
                    dp[i][r][g][0] = min(dp[i][r][g][0], dp[i-1][r-1][g][2] + get(cnt[kek[0][r-1]], r, g, i-r-g));
                }
            }
        }
        {
            for(int r=0; r<=min(i-1, cnt[n][0]); r++){
                for(int g=1; g<=min(i, cnt[n][1]); g++){
                    if(r + g > i)
                        continue;
                    dp[i][r][g][1] = min(dp[i][r][g][1], dp[i-1][r][g-1][0] + get(cnt[kek[1][g-1]], r, g, i-r-g));
                    dp[i][r][g][1] = min(dp[i][r][g][1], dp[i-1][r][g-1][2] + get(cnt[kek[1][g-1]], r, g, i-r-g));
                }
            }
        }
        {
            for(int r=0; r<=min(i, cnt[n][0]); r++){
                for(int g=0; g<=min(i, cnt[n][1]); g++){
                    if((i-r-g)<=0 || (i-r-g) > cnt[n][2])
                        continue;
                    dp[i][r][g][2] = min(dp[i][r][g][2], dp[i-1][r][g][0] + get(cnt[kek[2][i-r-g-1]], r, g, i-r-g));
                    dp[i][r][g][2] = min(dp[i][r][g][2], dp[i-1][r][g][1] + get(cnt[kek[2][i-r-g-1]], r, g, i-r-g));
                }
            }
        }
    }
    cout << *min_element(dp[n][cnt[n][0]][cnt[n][1]], dp[n][cnt[n][0]][cnt[n][1]]+3) << endl;
}

signed main(){
     fast_io();
//  ;(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

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

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:85:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |         kek[s[i-1]].pb(i);
      |                   ^

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