Submission #170509

#	Time	Username	Problem	Language	Result	Execution time	Memory
170509		stefdasca	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	77 ms	6520 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;

int n;
string s;
vector<int> v[4];
int dp[402][402][402][3];
bool viz[402][402][402][3];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> s;
    for(int i = 0; i < n; ++i)
    {
        if(s[i] == 'R')
            v[1].pb(i);
        if(s[i] == 'G')
            v[2].pb(i);
        if(s[i] == 'Y')
            v[3].pb(i);
    }
    viz[0][0][0][0] = viz[0][0][0][1] = viz[0][0][0][2] = 1;
    int mn = (1<<30);
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j <= i; ++j)
            for(int k = 0; k <= i; ++k)
                for(int lst = 0; lst <= 2; ++lst)
                {
                    if(!viz[i][j][k][lst])
                        continue;
                    int chR = j;
                    int chG = k;
                    int chY = i - j - k;
                    // next = rosu
                    if(chR < v[1].size() && lst != 0)
                    {
                        if(!viz[i+1][j+1][k][0] || dp[i+1][j+1][k][0] > dp[i][j][k][lst] + max(0, v[1][chR] - i))
                        {
                            dp[i+1][j+1][k][0] = dp[i][j][k][lst] + max(0, v[1][chR] - i);
                            viz[i+1][j+1][k][0] = 1;
                        }
                    }
                    if(chG < v[2].size() && lst != 1)
                    {
                        if(!viz[i+1][j][k+1][1] || dp[i+1][j][k+1][1] > dp[i][j][k][lst] + max(0, v[2][chG] - i))
                        {
                            dp[i+1][j][k+1][1] = dp[i][j][k][lst] + max(0, v[2][chG] - i);
                            viz[i+1][j][k+1][1] = 1;
                        }
                    }
                    if(chY < v[3].size() && lst != 2)
                    {
                        if(!viz[i+1][j][k][2] || dp[i+1][j][k][2] > dp[i][j][k][lst] + max(0, v[3][chY] - i))
                        {
                            dp[i+1][j][k][2] = dp[i][j][k][lst] + max(0, v[3][chY] - i);
                            viz[i+1][j][k][2] = 1;
                        }
                    }
                }
    }
    for(int i = 0; i <= 2; ++i)
        if(viz[n][(int)v[1].size()][(int)v[2].size()][i])
            mn = min(mn, dp[n][(int)v[1].size()][(int)v[2].size()][i]);
    if(mn == (1<<30))
        mn = -1;
    cout << mn;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:50:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(chR < v[1].size() && lst != 0)
                        ~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(chG < v[2].size() && lst != 1)
                        ~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(chY < v[3].size() && lst != 2)
                        ~~~~^~~~~~~~~~~~~

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