oj.uz

Submission #936045

# Submission time Handle Problem Language Result Execution time Memory
936045 2024-03-01T03:55:37 Z Marco_Escandon Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 500 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct st{ ll a,b,c; };
vector<st> cad[4];
ll cost(ll p1, ll p2, st asd, ll p)
{
    asd.a=max(cad[p1][p2].a,asd.a-1);
    asd.b=max(cad[p1][p2].b,asd.b-1);
    asd.c=max(cad[p1][p2].c,asd.c-1);
    return (asd.a+asd.b+asd.c-p);
}
int main()
{
    ll n;
    cin>>n;
    st asd={0,0,0};
    for(int i=0; i<4; i++)
        cad[i].push_back(asd),cad[i].push_back(asd);
    for(int i=1; i<=n; i++)
    {
        char temp;
        cin>>temp;
        if(temp=='R') asd.a++;
        if(temp=='G') asd.b++;
        if(temp=='Y') asd.c++;
        if(temp=='R') cad[1].push_back(asd);
        if(temp=='G') cad[2].push_back(asd);
        if(temp=='Y') cad[3].push_back(asd);
    }
    ll dp[4][n+2][n+2][n+2];
    
    for(int i=0; i<n+2; i++)
        for(int j=0; j<n+2; j++)
            for(int k=0; k<n+2; k++)
            dp[1][i][j][k]=dp[2][i][j][k]=dp[3][i][j][k]=1e9;
    dp[1][1][1][1]=0;
    dp[2][1][1][1]=0;
    dp[3][1][1][1]=0;
    ll sol=0;
    for(int i=1; i<cad[1].size(); i++)
    {
        for(int j=1; j<cad[2].size(); j++)
        {
            for(int k=1; k<cad[3].size(); k++)
            {
                ll asd=1e9;
                if(i+j+k<=3) continue;
                for(int pl=1; pl<4; pl++)
                {
                    ll temp=1e9;
                    if(pl==1)
                    {
                        if(j>1)
                        temp=min(temp,dp[2][i][j-1][k]+cost(2,j,{i,j,k},i+j+k-3));
                        if(k>1)
                        temp=min(temp,dp[3][i][j][k-1]+cost(3,k,{i,j,k},i+j+k-3));
                    }
                    if(pl==2)
                    {
                        if(i>1)
                        temp=min(temp,dp[1][i-1][j][k]+cost(1,i,{i,j,k},i+j+k-3));
                        if(k>1)
                        temp=min(temp,dp[3][i][j][k-1]+cost(3,k,{i,j,k},i+j+k-3));
                    }
                    if(pl==3)
                    {
                        if(i>1)
                        temp=min(temp,dp[1][i-1][j][k]+cost(1,i,{i,j,k},i+j+k-3));
                        if(j>1)
                        temp=min(temp,dp[2][i][j-1][k]+cost(2,j,{i,j,k},i+j+k-3));
                    }
                    asd=min(asd,temp);
                    dp[pl][i][j][k]=min(temp,dp[pl][i][j][k]);
                }
                sol=asd;
            }
        }
    }
    if(sol==1000000000)
    {
        cout<<"-1";
    }
    else {
        cout<<sol;
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 4 ms 7772 KB Output is correct
19 Correct 4 ms 7768 KB Output is correct
20 Correct 5 ms 7772 KB Output is correct
21 Correct 4 ms 7656 KB Output is correct
22 Correct 4 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 5 ms 7772 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 4 ms 7796 KB Output is correct
28 Correct 4 ms 7768 KB Output is correct
29 Correct 5 ms 7772 KB Output is correct
30 Correct 4 ms 7772 KB Output is correct
31 Correct 4 ms 7776 KB Output is correct
32 Correct 6 ms 7784 KB Output is correct
33 Correct 4 ms 7528 KB Output is correct
34 Correct 4 ms 7524 KB Output is correct
35 Correct 4 ms 7004 KB Output is correct
36 Correct 4 ms 7520 KB Output is correct
37 Correct 4 ms 6628 KB Output is correct
38 Correct 4 ms 7776 KB Output is correct
39 Correct 4 ms 7776 KB Output is correct
40 Correct 4 ms 7520 KB Output is correct
41 Correct 4 ms 7776 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 552 KB Output is correct
2 Execution timed out 807 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 436 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 436 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 4 ms 7772 KB Output is correct
19 Correct 4 ms 7768 KB Output is correct
20 Correct 5 ms 7772 KB Output is correct
21 Correct 4 ms 7656 KB Output is correct
22 Correct 4 ms 7772 KB Output is correct
23 Correct 4 ms 7772 KB Output is correct
24 Correct 4 ms 7772 KB Output is correct
25 Correct 5 ms 7772 KB Output is correct
26 Correct 4 ms 7772 KB Output is correct
27 Correct 4 ms 7796 KB Output is correct
28 Correct 4 ms 7768 KB Output is correct
29 Correct 5 ms 7772 KB Output is correct
30 Correct 4 ms 7772 KB Output is correct
31 Correct 4 ms 7776 KB Output is correct
32 Correct 6 ms 7784 KB Output is correct
33 Correct 4 ms 7528 KB Output is correct
34 Correct 4 ms 7524 KB Output is correct
35 Correct 4 ms 7004 KB Output is correct
36 Correct 4 ms 7520 KB Output is correct
37 Correct 4 ms 6628 KB Output is correct
38 Correct 4 ms 7776 KB Output is correct
39 Correct 4 ms 7776 KB Output is correct
40 Correct 4 ms 7520 KB Output is correct
41 Correct 4 ms 7776 KB Output is correct
42 Correct 0 ms 552 KB Output is correct
43 Execution timed out 807 ms 1048576 KB Time limit exceeded
44 Halted 0 ms 0 KB -