Submission #234490

#	Time	Username	Problem	Language	Result	Execution time	Memory
234490		nicolaalexandra	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	103 ms	163064 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define DIM 402
#define INF 2000000000
using namespace std;
int dp[DIM][DIM][DIM][3],cnt[3][DIM];
vector <int> poz[3];
char v[DIM];
int n,i,j,k;
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>v+1;
    for (i=1;i<=n;i++){
        cnt[0][i] = cnt[0][i-1];
        cnt[1][i] = cnt[1][i-1];
        cnt[2][i] = cnt[2][i-1];

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

    /// dp[nr0][nr1][nr2][0/1/2]

    for (i=0;i<=poz[0].size();i++)
        for (j=0;j<=poz[1].size();j++)
            for (k=0;k<=poz[2].size();k++)
                dp[i][j][k][0] = dp[i][j][k][1] = dp[i][j][k][2] = INF;

    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;

    int a = poz[0].size(), b = poz[1].size(), c = poz[2].size();

    for (i=1;i<=n;i++)
        for (int nr0=0;nr0<=min(i,a);nr0++)
            for (int nr1=0;nr1<=min(i,b) && nr0 + nr1 <= i;nr1++){
                int nr2 = i - nr0 - nr1;
                if (nr2 > c)
                    continue;

                /// incerc sa pun un 0
                if (nr0){
                    int pos = poz[0][nr0-1];
                    int val = max (cnt[1][pos] - nr1,0) + max (cnt[2][pos] - nr2,0);

                    if (dp[nr0-1][nr1][nr2][1] != INF)
                        dp[nr0][nr1][nr2][0] = min (dp[nr0][nr1][nr2][0], dp[nr0-1][nr1][nr2][1] + val);
                    if (dp[nr0-1][nr1][nr2][2] != INF)
                        dp[nr0][nr1][nr2][0] = min (dp[nr0][nr1][nr2][0], dp[nr0-1][nr1][nr2][2] + val);
                }

                /// incerc sa pun 1
                if (nr1){
                    int pos = poz[1][nr1-1];
                    int val = max (cnt[0][pos] - nr0,0) + max (cnt[2][pos] - nr2, 0);

                    if (dp[nr0][nr1-1][nr2][0] != INF)
                        dp[nr0][nr1][nr2][1] = min (dp[nr0][nr1][nr2][1], dp[nr0][nr1-1][nr2][0] + val);
                    if (dp[nr0][nr1-1][nr2][2] != INF)
                        dp[nr0][nr1][nr2][1] = min (dp[nr0][nr1][nr2][1], dp[nr0][nr1-1][nr2][2] + val);
                }


                /// incerec sa pun 2
                if (nr2){
                    int pos = poz[2][nr2-1];
                    int val = max (cnt[0][pos] - nr0,0) + max (cnt[1][pos] - nr1, 0);

                    if (dp[nr0][nr1][nr2-1][0] != INF)
                        dp[nr0][nr1][nr2][2] = min (dp[nr0][nr1][nr2][2], dp[nr0][nr1][nr2-1][0] + val);
                    if (dp[nr0][nr1][nr2-1][1] != INF)
                        dp[nr0][nr1][nr2][2] = min (dp[nr0][nr1][nr2][2], dp[nr0][nr1][nr2-1][1] + val);
                }
            }

    int sol = INF;
    sol = min (sol, dp[a][b][c][0]);
    sol = min (sol, dp[a][b][c][1]);
    sol = min (sol, dp[a][b][c][2]);

    if (sol == INF)
        cout<<-1;
    else cout<<sol;

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>n>>v+1;
             ~^~
joi2019_ho_t3.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<=poz[0].size();i++)
              ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j=0;j<=poz[1].size();j++)
                  ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k=0;k<=poz[2].size();k++)
                      ~^~~~~~~~~~~~~~~

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