oj.uz

Submission #916527

# Submission time Handle Problem Language Result Execution time Memory
916527 2024-01-26T04:11:11 Z ReLice Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 62 ms 319580 KB 
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template <class _T>
bool chmin(_T &x, const _T &y){
    bool f=0;
    if (x>y){x=y;f=1;}
    return f;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    bool f=0;
    if (x<y){x=y;f=1;}
    return f;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e9;
const ll mod=1e9+7;
const ll N=402;
const ld eps=1e-9;
ll dp[N][N][N][3];
void solve(){
    ll i,j,q,k;
    ll n;
    cin>>n;
    ll a[n+5];
    str s;
    cin>>s;
    vector<vll> v(3);
    for(i=0;i<n;i++){
        ll x;
        if(s[i]=='R')x=0;
        if(s[i]=='G')x=1;
        if(s[i]=='Y')x=2;
        a[i+1]=x;
        v[x].pb(i+1);
    }
    ll R=v[0].sz,G=v[1].sz,Y=v[2].sz;
    for(i=0;i<=R;i++)
        for(j=0;j<=G;j++)
            for(q=0;q<=Y;q++)
                for(k=0;k<3;k++)
                    dp[i][j][q][k]=inf;

    dp[0][0][0][0]=0;
    dp[0][0][0][1]=0;
    dp[0][0][0][2]=0;
    ll pref[n+5][3];
    memset(pref,0,sizeof(pref));
    for(i=1;i<=n;i++){
        for(j=0;j<3;j++){
            pref[i][j]=pref[i-1][j];
            if(a[i]==j)pref[i][j]++;
        }
    }
    for(i=0;i<=R;i++){
        for(j=0;j<=G;j++){
            for(q=0;q<=Y;q++){
                for(k=0;k<3;k++){
                    if(i<R && k!=0){
                        chmin(dp[i+1][j][q][0],dp[i][j][q][k]+max(0,pref[v[0][i]][1]-j)+max(0,pref[v[0][i]][2]-q));
                    }
                    if(j<G && k!=1){
                        chmin(dp[i][j+1][q][1],dp[i][j][q][k]+max(0,pref[v[1][j]][0]-i)+max(0,pref[v[1][j]][2]-q));
                    }
                    if(q<Y && k!=2){
                        chmin(dp[i][j][q+1][2],dp[i][j][q][k]+max(0,pref[v[2][j]][0]-i)+max(0,pref[v[2][j]][1]-j));
                    }
                }
            }
        }
    }
    ll ans=inf;
    for(i=0;i<3;i++){
        chmin(ans,dp[R][G][Y][i]);
    }
    if(ans==inf)cout<<-1<<endl;
    else cout<<ans<<endl;
}

signed main(){
	//start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*



*/

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:60:12: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |         v[x].pb(i+1);
      |            ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Incorrect 2 ms 10684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Incorrect 2 ms 10684 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 60 ms 318340 KB Output is correct
3 Correct 60 ms 319312 KB Output is correct
4 Correct 59 ms 319580 KB Output is correct
5 Correct 56 ms 319568 KB Output is correct
6 Correct 56 ms 319568 KB Output is correct
7 Correct 57 ms 318600 KB Output is correct
8 Correct 57 ms 318600 KB Output is correct
9 Correct 59 ms 318540 KB Output is correct
10 Correct 58 ms 319380 KB Output is correct
11 Correct 62 ms 319560 KB Output is correct
12 Correct 28 ms 197396 KB Output is correct
13 Correct 36 ms 261088 KB Output is correct
14 Correct 44 ms 286776 KB Output is correct
15 Correct 56 ms 318800 KB Output is correct
16 Correct 56 ms 319032 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Incorrect 2 ms 10684 KB Output isn't correct
6 Halted 0 ms 0 KB -