제출 #226043

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

joi2019_ho_t3

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

vector <int> v[3];
int dp[3][410][410][410];
char s[430];


int calcul (int nr0 , int nr1 , int nr2 , int curr){

    int poz , st , dr , mid;

    if (curr == 0)
        curr = v[0][nr0];
    else if (curr == 1)
        curr = v[1][nr1];
    else curr = v[2][nr2];

    /// curr e poz initiala

    poz = curr;
    if (!v[0].empty()){
        st = 0;
        dr = nr0 - 1;
        while (st <= dr){
            mid = (st + dr) / 2;
            if (v[0][mid] <= curr)
                st = mid + 1;
            else dr = mid - 1;
        }

        poz += (nr0 - st); /// st = primul mai mare decat curr
    }

    if (!v[1].empty()){
        st = 0;
        dr = nr1 - 1;
        while (st <= dr){
            mid = (st + dr) / 2;
            if (v[1][mid] <= curr)
                st = mid + 1;
            else dr = mid - 1;
        }

        poz += (nr1 - st); /// st = primul mai mare decat curr
    }

    if (!v[2].empty()){
        st = 0;
        dr = nr2 - 1;
        while (st <= dr){
            mid = (st + dr) / 2;
            if (v[2][mid] <= curr)
                st = mid + 1;
            else dr = mid - 1;
        }

        poz += (nr2 - st); /// st = primul mai mare decat curr

    }


    return poz - (nr0 + nr1 + nr2 + 1);
}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i , sum , j , k , sol;
    fscanf (fin,"%d\n",&n);
    fgets (s + 1 , 420 , fin); /// hehe

    for (i = n ; i ; i--){

        if (s[i] == 'R'){
            v[0].push_back(i);
        }
        else if (s[i] == 'G'){
            v[1].push_back(i);
        }
        else {
            v[2].push_back(i);
        }
    }

    reverse(v[0].begin() , v[0].end());
    reverse(v[1].begin() , v[1].end());
    reverse(v[2].begin() , v[2].end());


    /// dp[i][j][k][0 / 1 / 2] = i 0 , j 1 , k 2 , current e 0 / 1 / 2

    for (sum = 1 ; sum <= n ; sum++){

        for (i = 0 ; i <= v[0].size() ; i++){

            for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){

                k = sum - i - j;
                if (k >= 0 && k <= v[2].size()){
                    dp[0][i][j][k] = dp[1][i][j][k] = dp[2][i][j][k] = INF;
                }

            }

        }

    }

    if (!v[0].empty())
        dp[0][1][0][0] = v[0][0] - 1;

    if (!v[1].empty())
        dp[1][0][1][0] = v[1][0] - 1;

    if (!v[2].empty())
        dp[2][0][0][1] = v[2][0] - 1;

    /// initializari

    sol = 2000000000;

    for (sum = 2 ; sum <= n ; sum++){

        for (i = 0 ; i <= v[0].size() ; i++){

            for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){

                k = sum - i - j;
                if (k < 0 || k > v[2].size())
                    continue;


                /// acum calculezi propriu zis

                if (i){ /// incerci sa pui 0

                    dp[0][i][j][k] = min(dp[1][i - 1][j][k] , dp[2][i - 1][j][k]) + calcul(i - 1 , j , k , 0);

                }

                if (j){ /// incerci sa pui 1

                    dp[1][i][j][k] = min(dp[0][i][j - 1][k] , dp[2][i][j - 1][k]) + calcul(i , j - 1 , k , 1);

                }

                if (k){ /// incerci sa pui 2

                    dp[2][i][j][k] = min(dp[0][i][j][k - 1] , dp[1][i][j][k - 1]) + calcul(i , j , k - 1 , 2);

                }


                if (sum == n){
                    sol = min( min(sol , dp[0][i][j][k]) , min(dp[1][i][j][k] , dp[2][i][j][k]) );
                }


            }

        }

    }

    if (sol == INF)
        sol = -1;

    if (n == 1)
        sol = 0;

    fprintf (fout,"%d",sol);

    return 0;
}

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

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:96:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i <= v[0].size() ; i++){
                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:98:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
                          ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:101:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (k >= 0 && k <= v[2].size()){
                               ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:126:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i <= v[0].size() ; i++){
                      ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:128:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (j = 0 ; j <= v[1].size() && i + j <= sum ; j++){
                          ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:131:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (k < 0 || k > v[2].size())
                              ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:71:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d\n",&n);
     ~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fgets (s + 1 , 420 , fin); /// hehe
     ~~~~~~^~~~~~~~~~~~~~~~~~~

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