oj.uz

Submission #541433

# Submission time Handle Problem Language Result Execution time Memory
541433 2022-03-23T15:02:53 Z browntoad Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 70 ms 164064 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
 
const ll inf = (1ll<<60);
const int iinf=2147483647;
const ll mod = 998244353;
const ll maxn=405;
const double PI=acos(-1);
 
ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}
 
ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}
int dp[maxn][maxn][maxn][3];
int pos[3][maxn];
int cnt[3][maxn];
signed main(){
    IOS();
    int n; cin>>n;
    string str; cin>>str;
    str='$'+str;
    int tota=0, totb=0, totc=0;
    REP1(i,n){
        if (str[i]=='R') tota++;
        else if (str[i]=='G') totb++;
        else totc++;
    }
    REP(i,tota+1){
        REP(j,totb+1){
            REP(k,totc+1){
                REP(l, 3){
                    dp[i][j][k][l]=inf;
                }
                
            }
        }
    }
    REP1(i,n){
        REP(l, 3) cnt[l][i]=cnt[l][i-1];
        if (str[i]=='R') {
            cnt[0][i]++;
            pos[0][cnt[0][i]]=i;
        }
        else if (str[i]=='G') {
            cnt[1][i]++;
            pos[1][cnt[1][i]]=i;
        }
        else {
            cnt[2][i]++;
            pos[2][cnt[2][i]]=i;
        }
    }
    dp[0][0][0][0]=dp[0][0][0][1]=dp[0][0][0][2]=0;
    // 0 is R, 1 is G, 2 is Y
    REP(i, tota+1){
        REP(j, totb+1){
            REP(k, totc+1){
                if (i+j+k==0) continue;
                if (i>0){
                    int p=pos[0][i]-1;
                    dp[i][j][k][0]=min(dp[i-1][j][k][1], dp[i-1][j][k][2]);
                    dp[i][j][k][0]+=p-min(i-1, cnt[0][p])-min(j, cnt[1][p])-min(k, cnt[2][p]);
                }
                if (j>0){
                    int p=pos[1][j]-1;
                    dp[i][j][k][1]=min(dp[i][j-1][k][0], dp[i][j-1][k][2]);
                    dp[i][j][k][1]+=p-min(i, cnt[0][p])-min(j-1, cnt[1][p])-min(k, cnt[2][p]);
                }
                if (k>0){
                    int p=pos[2][k]-1;
                    dp[i][j][k][2]=min(dp[i][j][k-1][0], dp[i][j][k-1][1]);
                    dp[i][j][k][2]+=p-min(i, cnt[0][p])-min(j, cnt[1][p])-min(k-1, cnt[2][p]);
                }
            }
        }
    }
    int k=min({dp[tota][totb][totc][0], dp[tota][totb][totc][1], dp[tota][totb][totc][2]});
    if (k==inf) k=-1;
    cout<<k<<endl;
}
/*

3
YYG

*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 444 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 444 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 61 ms 163996 KB Output is correct
3 Correct 70 ms 163212 KB Output is correct
4 Correct 61 ms 164052 KB Output is correct
5 Correct 62 ms 163984 KB Output is correct
6 Correct 61 ms 164032 KB Output is correct
7 Correct 66 ms 163236 KB Output is correct
8 Correct 62 ms 163276 KB Output is correct
9 Correct 61 ms 162380 KB Output is correct
10 Correct 62 ms 163996 KB Output is correct
11 Correct 64 ms 164064 KB Output is correct
12 Correct 19 ms 44272 KB Output is correct
13 Correct 32 ms 77576 KB Output is correct
14 Correct 43 ms 112076 KB Output is correct
15 Correct 60 ms 163996 KB Output is correct
16 Correct 61 ms 163916 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 444 KB Output is correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -