제출 #1309724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309724		StefanSebez	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	282 ms	196364 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=410;
const ll INF=1e18;
void chmn(ll &x,ll y){x=min(x,y);}
vector<int>a,b,c;
ll dp[3][N/2][N/2][N/2];int n;
int Cost(int col,int i,int j,int k){
    int res=0;
    if(col==0){
        int lb=lower_bound(b.begin(),b.end(),a[i-1])-b.begin();
        res+=max(0,j-lb);
        lb=lower_bound(c.begin(),c.end(),a[i-1])-c.begin();
        res+=max(0,k-lb);
    }
    if(col==1){
        int lb=lower_bound(a.begin(),a.end(),b[j-1])-a.begin();
        res+=max(0,i-lb);
        lb=lower_bound(c.begin(),c.end(),b[j-1])-c.begin();
        res+=max(0,k-lb);
    }
    if(col==2){
        int lb=lower_bound(a.begin(),a.end(),c[k-1])-a.begin();
        res+=max(0,i-lb);
        lb=lower_bound(b.begin(),b.end(),c[k-1])-b.begin();
        res+=max(0,j-lb);
    }
    return res;
}
int main(){
    scanf("%i",&n);
    string s;cin>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='R')a.pb(i);
        if(s[i]=='G')b.pb(i);
        if(s[i]=='Y')c.pb(i);
    }
    if(max({a.size(),b.size(),c.size()})>n/2+2){
        printf("-1\n");
        return 0;
    }
    for(int i=0;i<=a.size();i++)for(int j=0;j<=b.size();j++)for(int k=0;k<=c.size();k++)for(int col=0;col<=2;col++)dp[col][i][j][k]=INF;
    for(int col=0;col<=2;col++)dp[col][a.size()][b.size()][c.size()]=0;
    for(int i=a.size();i>=0;i--){
        for(int j=b.size();j>=0;j--){
            for(int k=c.size();k>=0;k--){
                for(int col=0;col<=2;col++){
                    if(col!=0&&i)chmn(dp[0][i-1][j][k],dp[col][i][j][k]+Cost(0,i,j,k));
                    if(col!=1&&j)chmn(dp[1][i][j-1][k],dp[col][i][j][k]+Cost(1,i,j,k));
                    if(col!=2&&k)chmn(dp[2][i][j][k-1],dp[col][i][j][k]+Cost(2,i,j,k));
                }
            }
        }
    }
    ll res=min({dp[0][0][0][0],dp[1][0][0][0],dp[2][0][0][0]});
    if(res>=INF)res=-1;
    printf("%lld\n",res);
    return 0;
}

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

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~

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