oj.uz

Submission #368113

# Submission time Handle Problem Language Result Execution time Memory
368113 2021-02-19T14:36:02 Z vaaven Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
0 / 100
 290 ms 192748 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <stack>
#include <iomanip>
#include <bitset>
#include <map>
#include <cassert>
#include <array>
#include <queue>
#include <cstring>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
// #define int long  long
    
using namespace std;
    
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
    
const int inf = 1e9 + 228;
const ll infll = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ld eps = 1e-14;
    
    
void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("a.in", "r", stdin);
//    freopen("outputik.txt", "w", stdout);
}

int dp[401][202][202][3];
array<int, 3> cnt[401];
vi kek[3];

int get(array<int, 3> lol, int a, int b, int c){
    int ans = 0;
    ans += max(0, lol[0]-a);
    ans += max(0, lol[1]-b);
    ans += max(0, lol[2]-c);
    return ans;
}

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    for(auto &i:dp)
        for(auto &j:i)
            for(auto &l:j)
                for(auto &k:l)
                    k = inf;
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for(char &c:s){
        if(c == 'R')
            c = 0;
        else if(c == 'G')
            c = 1;
        else
            c = 2;
    }
    for(int i=1; i<=n; i++){
        kek[s[i-1]].pb(i);
    }
    for(int i=1; i<=n; i++){
        cnt[i] = cnt[i-1];
        cnt[i][s[i-1]]++;
    }
    if(max({cnt[n][0], cnt[n][1], cnt[n][2]}) > (n+1)/2){
        cout << -1 << endl;
    }
    for(int i=1; i<=n; i++){
        // cur == R
        {
            for(int r=1; r<=min(i, cnt[n][0]); r++){
                for(int g=0; g<=min(i-1, cnt[n][1]); g++){
                    if(r + g > i)
                        continue;
                    dp[i][r][g][0] = min(dp[i][r][g][0], dp[i-1][r-1][g][1] + get(cnt[kek[0][r-1]], r, g, i-r-g));
                    dp[i][r][g][0] = min(dp[i][r][g][0], dp[i-1][r-1][g][2] + get(cnt[kek[0][r-1]], r, g, i-r-g));
                }
            }
        }
        {
            for(int r=0; r<=min(i-1, cnt[n][0]); r++){
                for(int g=1; g<=min(i, cnt[n][1]); g++){
                    if(r + g > i)
                        continue;
                    dp[i][r][g][1] = min(dp[i][r][g][1], dp[i-1][r][g-1][0] + get(cnt[kek[1][g-1]], r, g, i-r-g));
                    dp[i][r][g][1] = min(dp[i][r][g][1], dp[i-1][r][g-1][2] + get(cnt[kek[1][g-1]], r, g, i-r-g));
                }
            }
        }
        {
            for(int r=0; r<=min(i, cnt[n][0]); r++){
                for(int g=0; g<=min(i, cnt[n][1]); g++){
                    if((i-r-g)<=0 || (i-r-g) > cnt[n][2])
                        continue;
                    dp[i][r][g][2] = min(dp[i][r][g][2], dp[i-1][r][g][0] + get(cnt[kek[2][i-r-g-1]], r, g, i-r-g));
                    dp[i][r][g][2] = min(dp[i][r][g][2], dp[i-1][r][g][1] + get(cnt[kek[2][i-r-g-1]], r, g, i-r-g));
                }
            }
        }
    }
    cout << *min_element(dp[n][cnt[n][0]][cnt[n][1]], dp[n][cnt[n][0]][cnt[n][1]]+3) << endl;
}

signed main(){
     fast_io();
//  ;(time(NULL));
    cout << fixed << setprecision(10);
    int q = 1;
//    cin >> q;
    while(q--)
        solve();
}

Compilation message

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:85:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   85 |         kek[s[i-1]].pb(i);
      |                   ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 192492 KB Output is correct
2 Correct 117 ms 192428 KB Output is correct
3 Correct 118 ms 192584 KB Output is correct
4 Correct 126 ms 192492 KB Output is correct
5 Correct 117 ms 192492 KB Output is correct
6 Correct 117 ms 192492 KB Output is correct
7 Correct 119 ms 192492 KB Output is correct
8 Correct 120 ms 192492 KB Output is correct
9 Correct 119 ms 192488 KB Output is correct
10 Incorrect 120 ms 192492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 192492 KB Output is correct
2 Correct 117 ms 192428 KB Output is correct
3 Correct 118 ms 192584 KB Output is correct
4 Correct 126 ms 192492 KB Output is correct
5 Correct 117 ms 192492 KB Output is correct
6 Correct 117 ms 192492 KB Output is correct
7 Correct 119 ms 192492 KB Output is correct
8 Correct 120 ms 192492 KB Output is correct
9 Correct 119 ms 192488 KB Output is correct
10 Incorrect 120 ms 192492 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 192620 KB Output is correct
2 Correct 262 ms 192620 KB Output is correct
3 Correct 259 ms 192492 KB Output is correct
4 Correct 266 ms 192620 KB Output is correct
5 Correct 259 ms 192492 KB Output is correct
6 Correct 256 ms 192492 KB Output is correct
7 Correct 268 ms 192748 KB Output is correct
8 Correct 257 ms 192620 KB Output is correct
9 Correct 274 ms 192492 KB Output is correct
10 Correct 260 ms 192612 KB Output is correct
11 Correct 290 ms 192492 KB Output is correct
12 Correct 140 ms 192620 KB Output is correct
13 Correct 165 ms 192620 KB Output is correct
14 Correct 198 ms 192492 KB Output is correct
15 Incorrect 283 ms 192620 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 192492 KB Output is correct
2 Correct 117 ms 192428 KB Output is correct
3 Correct 118 ms 192584 KB Output is correct
4 Correct 126 ms 192492 KB Output is correct
5 Correct 117 ms 192492 KB Output is correct
6 Correct 117 ms 192492 KB Output is correct
7 Correct 119 ms 192492 KB Output is correct
8 Correct 120 ms 192492 KB Output is correct
9 Correct 119 ms 192488 KB Output is correct
10 Incorrect 120 ms 192492 KB Output isn't correct
11 Halted 0 ms 0 KB -