제출 #127697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127697		arnold518	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	146 ms	163100 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 400;
const int INF = 1000000;

int N, ans;
char S[MAXN+10];

int dp[MAXN+10][MAXN+10][MAXN+10][3];
int rcnt[MAXN+10], gcnt[MAXN+10], ycnt[MAXN+10];
vector<int> rpos, gpos, ypos;

int main()
{
    int i, j;

    scanf("%d%s", &N, S+1);
    for(i=1; i<=N; i++)
    {
        rcnt[i]=rcnt[i-1]; gcnt[i]=gcnt[i-1]; ycnt[i]=ycnt[i-1];
        if(S[i]=='R') rpos.push_back(i), rcnt[i]++;
        if(S[i]=='G') gpos.push_back(i), gcnt[i]++;
        if(S[i]=='Y') ypos.push_back(i), ycnt[i]++;
        //printf("%d %d %d\n", rcnt[i], gcnt[i], ycnt[i]);
    }

    for(int r=0; r<=rpos.size(); r++)
    {
        for(int g=0; g<=gpos.size(); g++)
        {
            for(int y=0; y<=ypos.size(); y++)
            {
                dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=INF;
                if(r==0 && g==0 && y==0)
                {
                    dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=0;
                    continue;
                }
                int pos=r+g+y;
                if(r!=0) dp[r][g][y][0]=min(dp[r-1][g][y][1], dp[r-1][g][y][2])+max(0, gcnt[rpos[r-1]]-g)+max(0, ycnt[rpos[r-1]]-y);
                if(g!=0) dp[r][g][y][1]=min(dp[r][g-1][y][0], dp[r][g-1][y][2])+max(0, rcnt[gpos[g-1]]-r)+max(0, ycnt[gpos[g-1]]-y);
                if(y!=0) dp[r][g][y][2]=min(dp[r][g][y-1][0], dp[r][g][y-1][1])+max(0, rcnt[ypos[y-1]]-r)+max(0, gcnt[ypos[y-1]]-g);
                //printf("%d %d %d : %d %d %d\n", r, g, y, dp[r][g][y][0], dp[r][g][y][1], dp[r][g][y][2]);
            }
        }
    }
    ans=min(min(dp[rpos.size()][gpos.size()][ypos.size()][0], dp[rpos.size()][gpos.size()][ypos.size()][1]), dp[rpos.size()][gpos.size()][ypos.size()][2]);
    if(ans>=INF) ans=-1;
    printf("%d", ans);
}

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

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int r=0; r<=rpos.size(); r++)
                  ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int g=0; g<=gpos.size(); g++)
                      ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:36:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int y=0; y<=ypos.size(); y++)
                          ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:21: warning: unused variable 'pos' [-Wunused-variable]
                 int pos=r+g+y;
                     ^~~
joi2019_ho_t3.cpp:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
joi2019_ho_t3.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &N, S+1);
     ~~~~~^~~~~~~~~~~~~~~~~

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