oj.uz

Submission #953595

# Submission time Handle Problem Language Result Execution time Memory
953595 2024-03-26T09:51:18 Z Parsa_Fallahpour Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 361 ms 757772 KB 
/*
    Sag Template by ParsaF(RBS Master)
*/
 
// Heaven
 
#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC target("sse4")

using namespace std;

 
#define TOF_IO                                   ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y)                             freopen(x, "r", stdin); freopen(y, "w", stdout);
 
#define SEP                                      ' '
#define endl                                     '\n'
 
#define F                                        first
#define S                                        second
#define ALL(x)                                   (x).begin(), (x).end()
#define sz(x)                                    (x).size()
#define PB                                       push_back
#define MP(x, y)                                 make_pair(x, y)
 
#define toLower(x)                               transform(ALL(x), x.begin(), ::tolower)
#define toUpper(x)                               transform(ALL(x), x.begin(), ::toupper)
 
#define EDGE(arr, x, y)                          arr[x].PB(y), arr[y].PB(x)
#define WEDGE(arr, x, y, z)                      arr[x].PB({y, z}), arr[y].PB({x, z})
 
#define debug(x)                                 cerr << #x << ": " << x << endl
#define kill(x)                                  cout << x << endl, exit(0);
 
#define BIPC(x)                                  __builtin_popcount(x)
 
#define fD1(arr, ind, x)                         for(int i=0; i<ind; i++) arr[i] = x;
#define fD2(arr, ind1, ind2, x)                  for(int i=0; i<ind1; i++) for(int j=0; j<ind2; j++) arr[i][j] = x;
 
#define lc                                       (id << 1)
#define rc                                       ((id << 1) | 1)
#define isLeaf                                   r - l == 1

typedef int       ll; 
typedef long double     lld;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll N    = 401;
const ll MAXN = 1023;
const ll MT   = 323 + 0;
const ll sq   = 320;
 
const ll M    = 1e9 + 7;
const ll IM   = 1e9 + 9;
 
const ll LOG  = 11;
 
const ll INF  = 1e9 + 1; 
const lld EPS = 0.0000001;
 
ll prime[] = {1000000009, 1000000007, 988244353, 1000696969, 696969569, 1223232323};
 
 
/***********************************************************       Dark side of Heaven        ************************************************************/
 
/***************************************************************************************************************************************************/
 
 
ll POW(ll a, ll b, ll md); 
ll LIS(vector<ll>& v);
ll MOD(ll a, ll b);
 
void YES(bool flag);
void Yes(bool flag);
 
inline ll mod_add(ll a, ll b);
inline ll mod_neg(ll a, ll b);
inline ll mod_mlt(ll a, ll b);
 
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
void InverseofNumber(ll p); void InverseofFactorial(ll p); void factorial(ll p); ll nPr(ll N, ll R, ll p); ll nCr(ll N, ll R); void comb();
*/

ll n;

string s;

vector<ll> R, G, B;


ll dp[N][N][N][3];

ll AB(ll x)
{
    if(x<0) return 0;
    return x;
}

void solve()
{
    cin >> n;
    
    cin >> s;
    s = "$" + s;
    for(int i=1; i<=n; i++)
    {
        if(s[i] == 'R') R.PB(i);
        if(s[i] == 'G') G.PB(i);
        if(s[i] == 'Y') B.PB(i);
    }
    
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) for(int f=0; f<3; f++) dp[i][j][k][f] = INF;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    
    for(int i=0; i<n; i++)
    {
        for(int r=0; r<=i; r++)
        {
            for(int g=0; g<=i-r; g++)
            {
                ll b = i-g-r;
                if(sz(R) >= r+1) dp[r+1][g][b][0] = min(dp[r+1][g][b][0], min(dp[r][g][b][1], dp[r][g][b][2]) + AB(i+1-R[r]));
                if(sz(G) >= g+1) dp[r][g+1][b][1] = min(dp[r][g+1][b][1], min(dp[r][g][b][0], dp[r][g][b][2]) + AB(i+1-G[g]));
                if(sz(B) >= b+1) dp[r][g][b+1][2] = min(dp[r][g][b+1][2], min(dp[r][g][b][0], dp[r][g][b][1]) + AB(i+1-B[b]));
                
            }
        }
    }
    ll ans = min({dp[sz(R)][sz(G)][sz(B)][0], dp[sz(R)][sz(G)][sz(B)][1], dp[sz(R)][sz(G)][sz(B)][2]});
    
    cout << (ans == INF? -1 : ans) << endl;
}
 
/*
*/
 
int main()
{
    TOF_IO;
    
    ll nTest=1;
    //cin >> nTest;
    
    while(nTest--) solve();
	
    return 0;
}
 
/********************************************************       The line that separates heaven and hell        *******************************************************/
 
// HELL
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N] * factI[R]) % M * factI[N - R]) % M;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
 
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? MOD(a * POW(MOD(a * a, md), b / 2, md), md) : MOD(POW(MOD(a * a, md), b / 2, md), md)));}
ll MOD(ll a, ll b){return (a%b + b) % b;}
 
ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
 
void YES(bool flag){cout << (flag? "YES\n" : "NO\n");}
void Yes(bool flag){cout << (flag? "Yes\n" : "No\n");}
 
inline ll mod_add(ll a, ll b){ ll res = a + b; return (res >= M? res - M : res); }
inline ll mod_neg(ll a, ll b){ ll res = (abs(a - b) < M? a - b : (a - b) % M); return (res < 0? res + M : res); }
inline ll mod_mlt(ll a, ll b){ return (a * b % M); }

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:131:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |                 if(sz(R) >= r+1) dp[r+1][g][b][0] = min(dp[r+1][g][b][0], min(dp[r][g][b][1], dp[r][g][b][2]) + AB(i+1-R[r]));
      |                          ^
joi2019_ho_t3.cpp:132:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  132 |                 if(sz(G) >= g+1) dp[r][g+1][b][1] = min(dp[r][g+1][b][1], min(dp[r][g][b][0], dp[r][g][b][2]) + AB(i+1-G[g]));
      |                          ^
joi2019_ho_t3.cpp:133:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  133 |                 if(sz(B) >= b+1) dp[r][g][b+1][2] = min(dp[r][g][b+1][2], min(dp[r][g][b][0], dp[r][g][b][1]) + AB(i+1-B[b]));
      |                          ^
joi2019_ho_t3.cpp: In function 'll LIS(std::vector<int>&)':
joi2019_ho_t3.cpp:173:133: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 | ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
      |                                                                                                                                   ~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 4 ms 29020 KB Output is correct
8 Correct 3 ms 29016 KB Output is correct
9 Correct 4 ms 29020 KB Output is correct
10 Correct 4 ms 29020 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 4 ms 29020 KB Output is correct
8 Correct 3 ms 29016 KB Output is correct
9 Correct 4 ms 29020 KB Output is correct
10 Correct 4 ms 29020 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 332 ms 757528 KB Output is correct
3 Correct 326 ms 755324 KB Output is correct
4 Correct 322 ms 757332 KB Output is correct
5 Correct 344 ms 757552 KB Output is correct
6 Correct 324 ms 757452 KB Output is correct
7 Correct 361 ms 755488 KB Output is correct
8 Correct 324 ms 755232 KB Output is correct
9 Correct 320 ms 752068 KB Output is correct
10 Correct 328 ms 757556 KB Output is correct
11 Correct 330 ms 757772 KB Output is correct
12 Correct 75 ms 275564 KB Output is correct
13 Correct 148 ms 405076 KB Output is correct
14 Correct 206 ms 543624 KB Output is correct
15 Correct 336 ms 757696 KB Output is correct
16 Correct 338 ms 757400 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 4 ms 29020 KB Output is correct
6 Correct 3 ms 29020 KB Output is correct
7 Correct 4 ms 29020 KB Output is correct
8 Correct 3 ms 29016 KB Output is correct
9 Correct 4 ms 29020 KB Output is correct
10 Correct 4 ms 29020 KB Output is correct
11 Incorrect 3 ms 29020 KB Output isn't correct
12 Halted 0 ms 0 KB -