oj.uz

Submission #686539

# Submission time Handle Problem Language Result Execution time Memory
686539 2023-01-25T12:13:05 Z JooDdae Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 70 ms 162800 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int INF = 1e9;

int n, dp[444][444][444][3];
string s;
vector<int> r, g, y;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    for(int i=0;i<n;i++) {
        if(s[i] == 'R') r.push_back(i);
        if(s[i] == 'G') g.push_back(i);
        if(s[i] == 'Y') y.push_back(i);
    }

    for(int i=0;i<=r.size();i++) for(int j=0;j<=g.size();j++) for(int k=0;k<=y.size();k++) {
        if(!i && !j && !k) continue;

        for(int l=0;l<3;l++) dp[i][j][k][l] = INF;
        if(i) dp[i][j][k][0] = min(dp[i-1][j][k][1], dp[i-1][j][k][2]) + abs(i+j+k-1 - r[i-1]);
        if(j) dp[i][j][k][1] = min(dp[i][j-1][k][0], dp[i][j-1][k][2]) + abs(i+j+k-1 - g[j-1]);
        if(k) dp[i][j][k][2] = min(dp[i][j][k-1][0], dp[i][j][k-1][1]) + abs(i+j+k-1 - y[k-1]);
    }

    int ans = *min_element(dp[r.size()][g.size()][y.size()], dp[r.size()][g.size()][y.size()]+3);
    cout << (ans >= INF ? -1 : ans/2);
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<=r.size();i++) for(int j=0;j<=g.size();j++) for(int k=0;k<=y.size();k++) {
      |                 ~^~~~~~~~~~
joi2019_ho_t3.cpp:20:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<=r.size();i++) for(int j=0;j<=g.size();j++) for(int k=0;k<=y.size();k++) {
      |                                              ~^~~~~~~~~~
joi2019_ho_t3.cpp:20:76: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<=r.size();i++) for(int j=0;j<=g.size();j++) for(int k=0;k<=y.size();k++) {
      |                                                                           ~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 468 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 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Incorrect 1 ms 468 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 59 ms 162744 KB Output is correct
3 Correct 63 ms 161964 KB Output is correct
4 Correct 58 ms 162736 KB Output is correct
5 Correct 63 ms 162800 KB Output is correct
6 Correct 59 ms 162788 KB Output is correct
7 Correct 70 ms 161940 KB Output is correct
8 Correct 59 ms 161992 KB Output is correct
9 Correct 59 ms 161132 KB Output is correct
10 Correct 62 ms 162748 KB Output is correct
11 Correct 57 ms 162728 KB Output is correct
12 Correct 17 ms 43980 KB Output is correct
13 Correct 33 ms 77004 KB Output is correct
14 Correct 39 ms 111180 KB Output is correct
15 Correct 70 ms 162692 KB Output is correct
16 Correct 59 ms 162780 KB Output is correct

Subtask #4
0 / 25.0

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