oj.uz

Submission #866781

# Submission time Handle Problem Language Result Execution time Memory
866781 2023-10-27T03:59:54 Z 12345678 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 3 ms 4956 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=65;
int n, dp[nx][nx][nx][3], mp[100], qs[3][nx], r[3][nx], res=INT_MAX;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>s;
    mp['R']=0; mp['G']=1; mp['Y']=2;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<3; j++) qs[j][i]=qs[j][i-1];
        qs[mp[s[i-1]]][i]++;
        r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
    }
    //for (int i=1; i<=n; i++) cout<<i<<' '<<qs[0][i]<<' '<<qs[1][i]<<' '<<qs[2][i]<<'\n';
    //for (int i=1; i<=n; i++) cout<<i<<' '<<r[0][i]<<' '<<r[1][i]<<' '<<r[2][i]<<'\n';
    for (int i=0; i<=qs[0][n]; i++)
    {
        for (int j=0; j<=qs[1][n]; j++)
        {
            for (int k=0; k<=qs[2][n]; k++)
            {
                dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=1e6;
                if (i==0&&j==0&&k==0) dp[i][j][k][0]=dp[i][j][k][1]=dp[i][j][k][2]=0;
                if (i>0) 
                {
                    int c=r[0][i], f1=qs[1][c], f2=qs[2][c], cst=0;
                    if (f1>j) cst+=f1-j;
                    if (f2>k) cst+=f2-k;
                    dp[i][j][k][0]=min({dp[i-1][j][k][1]+cst, dp[i-1][j][k][2]+cst, dp[i][j][k][0]});
                }
                if (j>0)
                {
                    int c=r[1][j], f1=qs[0][c], f2=qs[2][c], cst=0;
                    if (f1>i) cst+=f1-i;
                    if (f2>k) cst+=f2-k;
                    dp[i][j][k][1]=min({dp[i][j-1][k][0]+cst, dp[i][j-1][k][2]+cst, dp[i][j][k][1]});
                }
                if (k>0)
                {
                    int c=r[2][k], f1=qs[0][c], f2=qs[1][c], cst=0;
                    if (f1>i) cst+=f1-i;
                    if (f2>j) cst+=f2-j;
                    //cout<<"here"<<' '<<cst<<' '<<c<<'\n';
                    dp[i][j][k][2]=min({dp[i][j][k-1][0]+cst, dp[i][j][k-1][1]+cst, dp[i][j][k][2]});
                }
                //cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k][0]<<' '<<dp[i][j][k][1]<<' '<<dp[i][j][k][2]<<'\n';
            }
        }
    }
    for (int i=0; i<3; i++) res=min(res, dp[qs[0][n]][qs[1][n]][qs[2][n]][i]);
    if (res==1e6) cout<<-1;
    else cout<<res;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:17:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |         qs[mp[s[i-1]]][i]++;
      |                     ^
joi2019_ho_t3.cpp:18:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
      |                    ^
joi2019_ho_t3.cpp:18:35: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |         r[mp[s[i-1]]][qs[mp[s[i-1]]][i]]=i;
      |                                   ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 0 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 1 ms 2508 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 1 ms 2396 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 3 ms 4956 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2396 KB Output is correct
25 Correct 0 ms 2396 KB Output is correct
26 Correct 1 ms 2396 KB Output is correct
27 Correct 1 ms 2396 KB Output is correct
28 Correct 1 ms 2396 KB Output is correct
29 Correct 1 ms 2396 KB Output is correct
30 Correct 1 ms 2396 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 1 ms 2508 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 1 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 1 ms 2396 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Runtime error 3 ms 4956 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -