제출 #1237732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237732		dssfsuper2	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	75 / 100	1099 ms	68912 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
using pii = pair<int, int>;
vector<int> treating;
int n;
unordered_map<string, int> situations;
int dpf(vector<int>& treating, int lc){
    string key = to_string(lc) + '|';
    for (int x : treating) key += to_string(x) + ',';
    if(situations.count(key)) return situations[key];
    bitset<3> hs;
    int res = 1000000000;
    int ri=0;
    vector<int> indexe(3);
    int nbt=0;
    for(auto thing:treating){
        if(thing>=3){
            nbt++;
        }
    }
    int tnt=0;
    if(nbt==n)return 0;
    for(int i = 0;i<n;i++){
        int thing = treating[i];
        if (thing<3 && !hs[thing] && thing!=lc){
            hs[thing]=1;
            treating[i]+=3;
            res=min(res, dpf(treating, thing)+tnt);

            nbt++;
            treating[i]-=3;
        }
        if(thing<3)tnt++;
    }
    situations[key]=res;
    return res;
}
signed main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        char x;cin>>x;
        if(x=='R'){
            treating.push_back(0);
        }
        if(x=='G'){
            treating.push_back(1);
        }
        if(x=='Y'){
            treating.push_back(2);
        }
    }
    int x = dpf(treating, -1);
    cout << (x==1000000000? -1 : x);
}

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