oj.uz

Submission #936944

# Submission time Handle Problem Language Result Execution time Memory
936944 2024-03-03T05:30:42 Z Maite_Morale Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
60 / 100
 13 ms 20316 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define MAX 405
#define oo 1e18
#define mod 1000000007
#define fast_in ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(0);
using namespace std;
typedef long long ll;
#define pll pair<ll , ll>
#define vll vector<ll>
#define vvll vector<vll>
#define vpll vector<pll>
 
ll t,n;
vll v[5];
string a;
ll dp[50][50][50][10],s[10]={0,0,0};
ll cost(vll x,ll z){
    ll r=0;//if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<"\n";
    for(int i=0;i<3;i++){
        if(i==z)continue;
        ll c=lower_bound(v[i].begin(),v[i].end(),v[z][x[z]-1])-v[i].begin();
        //if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<c<<" ";
        r+=max(0LL,c-x[i]);
    }//if(x[0]==1 && x[1]==0 && x[2]==2 && z==2)cout<<r<<"\n";
return r;
}
int main(){
    fast_in
    cin>>n>>a;
    for(int i=0;i<n;i++){
        if(a[i]=='R')v[0].push_back(i+1);
        if(a[i]=='G')v[1].push_back(i+1);
        if(a[i]=='Y')v[2].push_back(i+1);
    }
    for(int i=0;i<=v[0].size();i++){
        for(int j=0;j<=v[1].size();j++){
            for(int k=0;k<=v[2].size();k++){
                for(int h=0;h<3;h++){
                    //cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<".\n";
                    if(i+j+k==0){
                        dp[i][j][k][h]=0;
                     //   cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<".\n";
                        continue;
                    }
                    s[h]=1;dp[i][j][k][h]=oo;
                    //cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<"☺\n";
                    if(min(i-s[0],min(j-s[1],k-s[2]))<0){
                      //  cout<<i-s[0]<<" "<<j-s[1]<<" "<<k-s[2]<<"\n";
                     //   cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"_\n";
                        s[h]=0;
                        continue;
                    }
                    for(int h1=0;h1<3;h1++){
                        if(h1==h)continue;
                      
                      //  if(dp[i-s[0]][j-s[1]][k-s[2]][h1]>=dp[i][j][k][h])continue;
                    //    cout<<i-s[0]<<" "<<j-s[1]<<" "<<k-s[2]<<":"<<h1<<" "<<dp[i-s[0]][j-s[1]][k-s[2]][h1]<<"\n";
                        ll z=dp[i][j][k][h],w=dp[i-s[0]][j-s[1]][k-s[2]][h1],w1=cost({i,j,k},h);
                       // cout<<z<<" "<<w<<"+"<<w1<<"*-*\n";
                        dp[i][j][k][h]=min(z,w+w1);//cout<<i<<" "<<j<<" "<<k<<" "<<h<<"\n";
                       // cout<<dp[0][1][2][1]<<" "<<dp[0][1][2][2]<<"☻\n";
                     //   cout<<dp[i][j][k][h]/*<<"+"<<cost({i,j,k},h)*/<<" o-o\n";
                    }
                  //  cout<<i<<" "<<j<<" "<<k<<" "<<h<<" "<<dp[i][j][k][h]<<"\n";
                    s[h]=0;
                }
            }
        }
    }
    sort(dp[v[0].size()][v[1].size()][v[2].size()],dp[v[0].size()][v[1].size()][v[2].size()]+3);
    if(dp[v[0].size()][v[1].size()][v[2].size()][0]==oo)dp[v[0].size()][v[1].size()][v[2].size()][0]=-1;
    cout<<dp[v[0].size()][v[1].size()][v[2].size()][0];
return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<=v[0].size();i++){
      |                 ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j=0;j<=v[1].size();j++){
      |                     ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int k=0;k<=v[2].size();k++){
      |                         ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2512 KB Output is correct
16 Correct 1 ms 2396 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2512 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 6492 KB Output is correct
19 Correct 3 ms 4444 KB Output is correct
20 Correct 3 ms 6492 KB Output is correct
21 Correct 3 ms 4444 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 3 ms 4656 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 2 ms 6616 KB Output is correct
28 Correct 3 ms 4444 KB Output is correct
29 Correct 3 ms 6492 KB Output is correct
30 Correct 2 ms 4576 KB Output is correct
31 Correct 2 ms 4560 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Correct 2 ms 6748 KB Output is correct
34 Correct 2 ms 6748 KB Output is correct
35 Correct 3 ms 6492 KB Output is correct
36 Correct 3 ms 4444 KB Output is correct
37 Correct 2 ms 4444 KB Output is correct
38 Correct 3 ms 4444 KB Output is correct
39 Correct 3 ms 4444 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 2 ms 2652 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2548 KB Output is correct
2 Runtime error 13 ms 20316 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 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2512 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 6492 KB Output is correct
19 Correct 3 ms 4444 KB Output is correct
20 Correct 3 ms 6492 KB Output is correct
21 Correct 3 ms 4444 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 3 ms 4656 KB Output is correct
24 Correct 2 ms 2396 KB Output is correct
25 Correct 2 ms 8540 KB Output is correct
26 Correct 2 ms 6492 KB Output is correct
27 Correct 2 ms 6616 KB Output is correct
28 Correct 3 ms 4444 KB Output is correct
29 Correct 3 ms 6492 KB Output is correct
30 Correct 2 ms 4576 KB Output is correct
31 Correct 2 ms 4560 KB Output is correct
32 Correct 3 ms 4444 KB Output is correct
33 Correct 2 ms 6748 KB Output is correct
34 Correct 2 ms 6748 KB Output is correct
35 Correct 3 ms 6492 KB Output is correct
36 Correct 3 ms 4444 KB Output is correct
37 Correct 2 ms 4444 KB Output is correct
38 Correct 3 ms 4444 KB Output is correct
39 Correct 3 ms 4444 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 2 ms 2652 KB Output is correct
42 Correct 1 ms 2548 KB Output is correct
43 Runtime error 13 ms 20316 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -