oj.uz

Submission #127685

# Submission time Handle Problem Language Result Execution time Memory
127685 2019-07-10T00:33:30 Z arnold518 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 9 ms 636 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 200;
const int INF = 987654321;

int N, ans;
char S[MAXN+10];

int dp[MAXN+10][MAXN+10][MAXN+10][3];
int rcnt[MAXN+10], gcnt[MAXN+10], ycnt[MAXN+10];
vector<int> rpos, gpos, ypos;

int main()
{
    int i, j;

    scanf("%d%s", &N, S+1);
    for(i=1; i<=N; i++)
    {
        rcnt[i]=rcnt[i-1]; gcnt[i]=gcnt[i-1]; ycnt[i]=ycnt[i-1];
        if(S[i]=='R') rpos.push_back(i), rcnt[i]++;
        if(S[i]=='G') gpos.push_back(i), gcnt[i]++;
        if(S[i]=='Y') ypos.push_back(i), ycnt[i]++;
        //printf("%d %d %d\n", rcnt[i], gcnt[i], ycnt[i]);
    }


    for(int r=0; r<=rpos.size(); r++)
    {
        for(int g=0; g<=gpos.size(); g++)
        {
            for(int y=0; y<=ypos.size(); y++)
            {
                dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=INF;
                if(r==0 && g==0 && y==0)
                {
                    dp[r][g][y][0]=dp[r][g][y][1]=dp[r][g][y][2]=0;
                    continue;
                }
                if(r!=0) dp[r][g][y][0]=min(dp[r-1][g][y][1], dp[r-1][g][y][2])+max(0, r+g+y-rpos[r-1]);
                else dp[r][g][y][0]=INF;
                if(g!=0) dp[r][g][y][1]=min(dp[r][g-1][y][0], dp[r][g-1][y][2])+max(0, r+g+y-gpos[g-1]);
                else dp[r][g][y][1]=INF;
                if(y!=0) dp[r][g][y][2]=min(dp[r][g][y-1][0], dp[r][g][y-1][1])+max(0, r+g+y-ypos[y-1]);
                else dp[r][g][y][2]=INF;
                //printf("%d %d %d : %d %d %d\n", r, g, y, dp[r][g][y][0], dp[r][g][y][1], dp[r][g][y][2]);
            }
        }
    }
    ans=min(min(dp[rpos.size()][gpos.size()][ypos.size()][0], dp[rpos.size()][gpos.size()][ypos.size()][1]), dp[rpos.size()][gpos.size()][ypos.size()][2]);
    if(ans>=INF) ans=-1;
    printf("%d", ans);
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int r=0; r<=rpos.size(); r++)
                  ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int g=0; g<=gpos.size(); g++)
                      ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int y=0; y<=ypos.size(); y++)
                          ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
joi2019_ho_t3.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &N, S+1);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Incorrect 2 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Incorrect 2 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 9 ms 636 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Incorrect 2 ms 504 KB Output isn't correct
12 Halted 0 ms 0 KB -