oj.uz

Submission #123059

# Submission time Handle Problem Language Result Execution time Memory
123059 2019-06-30T06:53:57 Z Alliance Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 567004 KB 
// In the Name of Allah
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 70;
const ll MOD = 1e9+7;
using namespace std;

int dp[MAX_N][MAX_N][MAX_N][MAX_N][3];
int a[MAX_N];
int n;

void readinput()
{
    cin >> n;
    string s;
    cin >> s;
    for(int i = 1;i<=n;++i)
    {
        if (s[i-1]=='R')
            a[i] = 0;
        else if (s[i-1]=='G')
            a[i] = 1;
        else
            a[i] = 2;
    }
}

void mini(int &a,int b)
{
    a = min(a,b);
}

int main()
{
    readinput();
    for(int i = 0;i<MAX_N;++i)
        for(int j = 0;j<MAX_N;++j)
            for(int k = 0;k<MAX_N;++k)
                for(int t = 0;t<MAX_N;++t)
                    for(int l = 0;l<3;++l)
                        dp[i][j][k][t][l] = 1e9;
    dp[1][0][0][0][a[1]] = 0;
    for(int i = 2;i<=n;++i)
    {
        for(int x1 = 0;x1<i;++x1)
        {
            for(int x2 = 0;x2<i;++x2)
            {
                for(int x3 = 0;x3<i;++x3)
                {
                    for(int j = 0;j<3;++j)
                    {
                        int s = x1+x2+x3;
                        if (j==a[i])
                        {
                            if (a[i]==0)
                                mini(dp[i][x1+1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s+1);
                            if (a[i]==1)
                                mini(dp[i][x1][x2+1][x3][j],dp[i-1][x1][x2][x3][j]+s+1);
                            if (a[i]==2)
                                mini(dp[i][x1][x2][x3+1][j],dp[i-1][x1][x2][x3][j]+s+1);
                        }
                        else
                            mini(dp[i][x1][x2][x3][a[i]],dp[i-1][x1][x2][x3][j]+s);
                        if (a[i]==0)
                        {
                            if (x2)
                                mini(dp[i][x1][x2-1][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x3)
                                mini(dp[i][x1][x2][x3-1][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                        else if (a[i]==1)
                        {
                            if (x1)
                                mini(dp[i][x1-1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x3)
                                mini(dp[i][x1][x2][x3-1][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                        else
                        {
                            if (x2)
                                mini(dp[i][x1][x2-1][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                            if (x1)
                                mini(dp[i][x1-1][x2][x3][j],dp[i-1][x1][x2][x3][j]+s-1);
                        }
                    }
                }
            }
        }
    }
    vector<int> vc;
    for(int i = 0;i<3;++i)
    {
        if (dp[n][0][0][0][i]<=n*n*n)
            vc.push_back(dp[n][0][0][0][i]);
    }
    if (!vc.size())
        cout << -1;
    else
    {
        sort(vc.begin(),vc.end());
        cout << vc[0];
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 282232 KB Output is correct
2 Correct 235 ms 282184 KB Output is correct
3 Correct 235 ms 282232 KB Output is correct
4 Incorrect 238 ms 282360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 282232 KB Output is correct
2 Correct 235 ms 282184 KB Output is correct
3 Correct 235 ms 282232 KB Output is correct
4 Incorrect 238 ms 282360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 282220 KB Output is correct
2 Runtime error 839 ms 567004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 282232 KB Output is correct
2 Correct 235 ms 282184 KB Output is correct
3 Correct 235 ms 282232 KB Output is correct
4 Incorrect 238 ms 282360 KB Output isn't correct
5 Halted 0 ms 0 KB -