oj.uz

Submission #200224

# Submission time Handle Problem Language Result Execution time Memory
200224 2020-02-05T17:24:27 Z mdn2002 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 500 ms 854136 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,dp[5][352][352][352];
vector<int>v[4];
string s;
int f(int x,int ir,int ig,int iy)
{
    if(ir+ig+iy==n)return 0;
    if(dp[x][ir][ig][iy]!=-1)return dp[x][ir][ig][iy];
    int ans=1e9,ind=ir+ig+iy,id;
    for(int i=0;i<3;i++)
    {
        if(i==x)continue;
        if(i==0)
        {
            if(ir==v[0].size())continue;
            int id=v[i][ir],ad=0;
            ad-=lower_bound(v[1].begin(),v[1].begin()+ig,id)-v[1].begin();
            ad+=ig;
            ad-=lower_bound(v[2].begin(),v[2].begin()+iy,id)-v[2].begin();
            ad+=iy;
            ans=min(ans,f(0,ir+1,ig,iy)+abs((id+ad)-ind));
        }
        if(i==1)
        {
            if(ig==v[1].size())continue;
            int id=v[i][ig],ad=0;
            ad-=lower_bound(v[0].begin(),v[0].begin()+ir,id)-v[0].begin();
            ad+=ir;
            ad-=lower_bound(v[2].begin(),v[2].begin()+iy,id)-v[2].begin();
            ad+=iy;
            ans=min(ans,f(1,ir,ig+1,iy)+abs((id+ad)-ind));
        }
        if(i==2)
        {
            if(iy==v[2].size())continue;
            int id=v[i][iy],ad=0;
            ad-=lower_bound(v[1].begin(),v[1].begin()+ig,id)-v[1].begin();
            ad+=ig;
            ad-=lower_bound(v[0].begin(),v[0].begin()+ir,id)-v[0].begin();
            ad+=ir;
            ans=min(ans,f(2,ir,ig,iy+1)+abs((id+ad)-ind));
        }
    }
    return dp[x][ir][ig][iy]=ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("dec.in","r",stdin);
    //freopen("dec.out","w",stdout);
    memset(dp,-1,sizeof dp);
    cin>>n>>s;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='R')v[0].push_back(i);
        if(s[i]=='G')v[1].push_back(i);
        if(s[i]=='Y')v[2].push_back(i);
    }
    int mx=max(v[0].size(),max(v[1].size(),v[2].size()));
    if(mx-1>n-mx)
    {
        cout<<-1;
        return 0;
    }
    int ans=f(3,0,0,0);
    cout<<ans;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ir==v[0].size())continue;
                ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(ig==v[1].size())continue;
                ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(iy==v[2].size())continue;
                ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:11:30: warning: unused variable 'id' [-Wunused-variable]
     int ans=1e9,ind=ir+ig+iy,id;
                              ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 624 ms 853988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 624 ms 853988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 853872 KB Output is correct
2 Correct 496 ms 853840 KB Output is correct
3 Correct 478 ms 853996 KB Output is correct
4 Correct 463 ms 853880 KB Output is correct
5 Correct 465 ms 853880 KB Output is correct
6 Correct 478 ms 854136 KB Output is correct
7 Correct 486 ms 853880 KB Output is correct
8 Correct 466 ms 854124 KB Output is correct
9 Correct 459 ms 854008 KB Output is correct
10 Correct 456 ms 853880 KB Output is correct
11 Correct 471 ms 854008 KB Output is correct
12 Correct 466 ms 853880 KB Output is correct
13 Correct 470 ms 853880 KB Output is correct
14 Correct 457 ms 853880 KB Output is correct
15 Correct 466 ms 853856 KB Output is correct
16 Correct 471 ms 853880 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 624 ms 853988 KB Time limit exceeded
2 Halted 0 ms 0 KB -