oj.uz

Submission #366086

# Submission time Handle Problem Language Result Execution time Memory
366086 2021-02-13T04:49:59 Z dolphingarlic Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 1009900 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

vector<int> has[4];
int dp[401][401][401][4];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        if (c == 'R') has[1].push_back(i);
        if (c == 'G') has[2].push_back(i);
        if (c == 'Y') has[3].push_back(i);
    }
    memset(dp, 0x3f, sizeof dp);
    dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][3] = 0;
    for (int i = 0; i <= has[1].size(); i++)
        for (int j = 0; j <= has[2].size(); j++)
            for (int k = 0; k <= has[3].size(); k++) {
                int tot = i + j + k;
                if (i) dp[i][j][k][1] = min(dp[i - 1][j][k][2], dp[i - 1][j][k][3]) + abs(has[1][i - 1] - tot);
                if (j) dp[i][j][k][2] = min(dp[i][j - 1][k][1], dp[i][j - 1][k][3]) + abs(has[2][j - 1] - tot);
                if (k) dp[i][j][k][3] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][2]) + abs(has[3][k - 1] - tot);
            }
    int ans = *min_element(dp[has[1].size()][has[2].size()][has[3].size()] + 1, dp[has[1].size()][has[2].size()][has[3].size()] + 4);
    if (ans > INF) cout << -1;
    else cout << ans / 2;
    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i <= has[1].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for (int j = 0; j <= has[2].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:24:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |             for (int k = 0; k <= has[3].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 742 ms 1009900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 742 ms 1009900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 549 ms 1009864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 742 ms 1009900 KB Time limit exceeded
2 Halted 0 ms 0 KB -