제출 #1231370

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

joi2019_ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
using namespace std;
#define int long long
using pii = pair<int, int>;

vector<int> treating;
int n;
map<int, int> situations;
int pow(int a, int b){
    if (b==0)return 1LL;
    return a*pow(a, b-1);
}
int superhash(vector<int>& treating, int lc){
    int meganumber = 1000000007;
    int supernumber = 1;
    int res=0;
    res+=(lc*supernumber)%meganumber;
    supernumber=(734*supernumber+3)%meganumber;
    for(auto thing:treating){
        res+=(thing*supernumber)%meganumber;
        supernumber=(734*supernumber+3)%meganumber;
    }
    return res;
}
int dpf(vector<int>& treating, int lc){
    int megahash=superhash(treating, lc);
    if(situations[megahash]!=0)return situations[megahash]-1;
    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[megahash]=res+1;
    return res;
}
//ok no I put in treating a big 4 to say it has been treated and order kepts
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