oj.uz

Submission #948176

# Submission time Handle Problem Language Result Execution time Memory
948176 2024-03-17T19:11:30 Z Zena_Hossam Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 500 ms 1048576 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
using namespace std;
namespace __gnu_pbds
{
typedef tree<ll,
        null_type,
        less_equal<ll>,
        rb_tree_tag,
        tree_order_statistics_node_update> ordered_set;
}
using namespace __gnu_pbds;
#define fi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//#define ll double

#define ll1 long long
#define F first
#define S second
#define sz size()
#define all(s) s.begin(),s.end()
#define all1(s) s.rbegin(),s.rend()
int main()
{
    //freopen("stdin.in","r",stdin);freopen("stdout.out","w",stdout);
    //cin>>T;ll oo=0;

    ll n;
    cin>>n;
    string s;
    cin>>s;
    map<ll,ll>m;
    map<ll,map<ll,ll>>d;
    ll arr[n];
    for(ll i=0; i<n; i++)
    {
        ll a=0;
        if(s[i]=='R')a=0;
        else if(s[i]=='G')a=1;
        else a=2;
        m[a]++;
        d[a][m[a]]=i;
    }
    ll dp[n+5][m[0]+5][m[1]+5][m[2]+5][5];
    for(ll a=0; a<=m[0]+4; a++)
    {
        for(ll b=0; b<=m[1]+4; b++)
        {
            for(ll c=0; c<=m[2]+4; c++)
            {
                for(ll i=0; i<=n+4; i++)
                {
                    for(ll j=0; j<=4; j++)
                        dp[i][a][b][c][j]=1e18;
                }
            }
        }
    }
    dp[0][0][0][0][1]=0;dp[0][0][0][0][0]=0;dp[0][0][0][0][2]=0;
    for(ll i=0; i<=n; i++)
    {
        for(ll a=0; a<=m[0]; a++)
        {
            for(ll b=0; b<=m[1]; b++)
            {
                for(ll c=0; c<=m[2]; c++)
                {
                    if(a+b+c==i)
                    {
                       // if(c<m[2])
                       // {
                            dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][0]+max(d[2][c+1]-i,0ll));
                            dp[i+1][a][b][c+1][2]=min(dp[i+1][a][b][c+1][2],dp[i][a][b][c][1]+max(d[2][c+1]-i,0ll));
                        //}
                        //if(b<m[1])
                        //{
                            dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][0]+max(d[1][b+1]-i,0ll));
                            dp[i+1][a][b+1][c][1]=min(dp[i+1][a][b+1][c][1],dp[i][a][b][c][2]+max(d[1][b+1]-i,0ll));
                        //}
                        //if(a<m[0])
                        //{
                            dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][2]+max(d[0][a+1]-i,0ll));
                            dp[i+1][a+1][b][c][0]=min(dp[i+1][a+1][b][c][0],dp[i][a][b][c][1]+max(d[0][a+1]-i,0ll));
                        //}
                    }
                }
            }
        }
    }
    if(min({dp[n][m[0]][m[1]][m[2]][0],dp[n][m[0]][m[1]][m[2]][1],dp[n][m[0]][m[1]][m[2]][2]})==1e18)cout<<-1;
    else
    cout<<min({dp[n][m[0]][m[1]][m[2]][0],dp[n][m[0]][m[1]][m[2]][1],dp[n][m[0]][m[1]][m[2]][2]});
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:35:8: warning: unused variable 'arr' [-Wunused-variable]
   35 |     ll arr[n];
      |        ^~~

Subtask #1
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 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 1116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
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 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 1116 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Execution timed out 579 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 348 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 604 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Incorrect 1 ms 1116 KB Output isn't correct
12 Halted 0 ms 0 KB -