oj.uz

Submission #642310

# Submission time Handle Problem Language Result Execution time Memory
642310 2022-09-19T08:24:30 Z danikoynov Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 74 ms 162968 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 410, inf = 1e9;

int n, a[maxn], dp[maxn][maxn][maxn][3];
string s;
vector < int > pos[3];
void solve()
{
    cin >> n >> s;
    for (int i = 0; i < n; i ++)
    {
        if (s[i] == 'R')
            a[i + 1] = 0;
        else if (s[i] == 'G')
            a[i + 1] = 1;
        else if (s[i] == 'Y')
            a[i + 1] = 2;
    }

    for (int i = 1; i <= n; i ++)
        pos[a[i]].push_back(i);

    for (int i = 0; i <= pos[0].size(); i ++)
        for (int j = 0; j <= pos[1].size(); j ++)
            for (int k = 0; k <= pos[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;

    for (int p = 0; p < n; p ++)
    {
        for (int i = 0; i <= min(p, (int)pos[0].size()); i ++)
            for (int j = 0; j <= min(p - i, (int)(pos[1].size())); j ++)
            {
                int k = p - i - j;
                if (k > pos[2].size())
                    continue;

                ///cout << i << " " << j << " " << k << " " << dp[i][j][k][0] << endl;
                if (i < (int)pos[0].size())
                {
                    int add0 = min(dp[i][j][k][1], dp[i][j][k][2]) + max(0, pos[0][i] - (p + 1));
                    dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], add0);
                }

                if (j < (int)pos[1].size())
                {
                    ///cout << "here" << endl;
                    int add1 = min(dp[i][j][k][0], dp[i][j][k][2]) + max(0, pos[1][j] - (p + 1));
                    dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], add1);
                }

                if (k < (int)pos[2].size())
                {
                    int add2 = min(dp[i][j][k][0], dp[i][j][k][1]) + max(0, pos[2][k] - (p + 1));
                    dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], add2);
                }
            }
    }
    ///cout << dp[1][1][0][1] << endl;


    int ans = inf;
    for (int last = 0; last < 3; last ++)
        ans = min(ans, dp[pos[0].size()][pos[1].size()][pos[2].size()][last]);

    if (ans >= inf)
        cout << -1 << endl;
    else
        cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i <= pos[0].size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for (int j = 0; j <= pos[1].size(); j ++)
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:45:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for (int k = 0; k <= pos[2].size(); k ++)
      |                             ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 if (k > pos[2].size())
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 572 KB Output is correct
11 Incorrect 1 ms 440 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 572 KB Output is correct
11 Incorrect 1 ms 440 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 64 ms 162900 KB Output is correct
3 Correct 64 ms 162172 KB Output is correct
4 Correct 67 ms 162968 KB Output is correct
5 Correct 64 ms 162892 KB Output is correct
6 Correct 69 ms 162892 KB Output is correct
7 Correct 65 ms 162288 KB Output is correct
8 Correct 63 ms 162052 KB Output is correct
9 Correct 70 ms 161296 KB Output is correct
10 Correct 64 ms 162936 KB Output is correct
11 Correct 66 ms 162948 KB Output is correct
12 Correct 18 ms 43988 KB Output is correct
13 Correct 32 ms 77136 KB Output is correct
14 Correct 51 ms 111288 KB Output is correct
15 Correct 74 ms 162860 KB Output is correct
16 Correct 66 ms 162896 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 0 ms 440 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 572 KB Output is correct
11 Incorrect 1 ms 440 KB Output isn't correct
12 Halted 0 ms 0 KB -