oj.uz

Submission #879157

# Submission time Handle Problem Language Result Execution time Memory
879157 2023-11-26T14:12:45 Z niter Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
100 / 100
 277 ms 485096 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());

int a[405], cnt[3];
vector<int> pos[3];
int dp[405][405][405][3], pref[405][3];
int from[405][405][405][3];
bool vis[405][405][405][3];
const int INF = 1e8;

inline void upd(int &x, int y){
    x = min(x, y);
}
inline int pos_diff(int ca, int cb, int cc, int last){
    int now = ca + cb + cc - 1; // 0-based
    if(last == 0){
        return max(pref[pos[0][ca]][1] - cb, 0) + max(pref[pos[0][ca]][2] - cc, 0);
    }
    if(last == 1){
        return max(pref[pos[1][cb]][0] - ca, 0) + max(pref[pos[1][cb]][2] - cc, 0);
    }
    if(last == 2){
        return max(pref[pos[2][cc]][0] - ca, 0) + max(pref[pos[2][cc]][1] - cb, 0);
    }
}
int cac(int ca, int cb, int cc, int last){
    if(ca < 0 || cb < 0 || cc < 0) return INF;
    if(ca == 0 && cb == 0 && cc == 0) return 0;
    if(last == 0 && ca == 0) return INF;
    if(last == 1 && cb == 0) return INF;
    if(last == 2 && cc == 0) return INF;
    if(vis[ca][cb][cc][last]) return dp[ca][cb][cc][last];
    loop(i,0,3){
        if(i == last) continue;
        int ret = cac(ca-(last == 0), cb-(last == 1), cc-(last == 2), i) + pos_diff(ca, cb, cc, last);
//        if(ca == 5)
//        if(cb == 7)
//        if(cc == 3)
//        if(i == 2){
//            op(ret)
//            op(ca - ((last) == 0))
//            op(cb - ((last) == 1))
//            op(cc - ((last) == 2))
//            op(dp[ca-(last == 0)][cb-(last == 1)][cc-(last == 2)][i])
//        }
        upd(dp[ca][cb][cc][last], ret);
        if(dp[ca][cb][cc][last] == ret) from[ca][cb][cc][last] = i;
    }
    vis[ca][cb][cc][last] = true;
    if(dp[ca][cb][cc][last] >= INF) from[ca][cb][cc][last] = -1;
    return dp[ca][cb][cc][last];
}

void trans(int ca, int cb, int cc, int la){
    if(ca + cb + cc == 0) return;
    int fr = from[ca][cb][cc][la];
    trans(ca - (la == 0), cb - (la == 1), cc - (la == 2), fr);
    opa(ca) opa(cb) opa(cc) opa(la)
    op(dp[ca][cb][cc][la])
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("in.txt", "r", stdin);
    int n; string s;
    cin >> n >> s;
    loop(i,0,3) pos[i].pb(-999);
    loop(i,0,n){
        if(s[i] == 'R') a[i] = 0;
        else if(s[i] == 'G') a[i] = 1;
        else a[i] = 2;
        cnt[a[i]]++;
        pos[a[i]].pb(i);
        pref[i][a[i]]++;
        if(i != 0) loop(j,0,3){
            pref[i][j] += pref[i-1][j];
        }
    }
//    loop(i,0,3){
//        opa(i) STL(pos[i])
//    }
    loop(i,0,cnt[0]+1)
        loop(j,0,cnt[1]+1)
            loop(k,0,cnt[2]+1)
                loop(l,0,3)
                    dp[i][j][k][l] = INF;
    loop(i,0,3){
        vis[0][0][0][i] = true;
        dp[0][0][0][i] = 0;
    }
    int ans = INF;
    loop(i,0,3){
        if(cnt[i] != 0){
            cac(cnt[0], cnt[1], cnt[2], i);
            ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
//            opa(i) op(dp[cnt[0]][cnt[1]][cnt[2]][i])
        }
    }
//    trans(cnt[0], cnt[1], cnt[2], from[cnt[0]][cnt[1]][cnt[2]][2]);
    if(ans == INF) cout << "-1\n";
    else cout << ans << '\n';
}
/*
222000001111111

212010101010121
*/

Compilation message

joi2019_ho_t3.cpp: In function 'int pos_diff(int, int, int, int)':
joi2019_ho_t3.cpp:30:9: warning: unused variable 'now' [-Wunused-variable]
   30 |     int now = ca + cb + cc - 1; // 0-based
      |         ^~~
joi2019_ho_t3.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 14680 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 33112 KB Output is correct
11 Correct 3 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 26972 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 4 ms 33116 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 14680 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 33112 KB Output is correct
11 Correct 3 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 26972 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 4 ms 33116 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 28 ms 93204 KB Output is correct
19 Correct 10 ms 76892 KB Output is correct
20 Correct 15 ms 101596 KB Output is correct
21 Correct 9 ms 80916 KB Output is correct
22 Correct 11 ms 97116 KB Output is correct
23 Correct 9 ms 70568 KB Output is correct
24 Correct 5 ms 43868 KB Output is correct
25 Correct 16 ms 117596 KB Output is correct
26 Correct 15 ms 121692 KB Output is correct
27 Correct 13 ms 109772 KB Output is correct
28 Correct 10 ms 85080 KB Output is correct
29 Correct 10 ms 89180 KB Output is correct
30 Correct 8 ms 70748 KB Output is correct
31 Correct 7 ms 64604 KB Output is correct
32 Correct 9 ms 74972 KB Output is correct
33 Correct 11 ms 101208 KB Output is correct
34 Correct 9 ms 88924 KB Output is correct
35 Correct 11 ms 93348 KB Output is correct
36 Correct 9 ms 80904 KB Output is correct
37 Correct 6 ms 56152 KB Output is correct
38 Correct 7 ms 60320 KB Output is correct
39 Correct 9 ms 76772 KB Output is correct
40 Correct 1 ms 4444 KB Output is correct
41 Correct 4 ms 37468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8736 KB Output is correct
2 Correct 105 ms 374524 KB Output is correct
3 Correct 43 ms 374272 KB Output is correct
4 Correct 42 ms 374480 KB Output is correct
5 Correct 41 ms 374524 KB Output is correct
6 Correct 43 ms 378196 KB Output is correct
7 Correct 43 ms 377172 KB Output is correct
8 Correct 42 ms 375856 KB Output is correct
9 Correct 45 ms 375888 KB Output is correct
10 Correct 44 ms 377936 KB Output is correct
11 Correct 43 ms 376660 KB Output is correct
12 Correct 39 ms 362580 KB Output is correct
13 Correct 38 ms 349788 KB Output is correct
14 Correct 36 ms 350744 KB Output is correct
15 Correct 49 ms 366676 KB Output is correct
16 Correct 41 ms 366928 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 14680 KB Output is correct
5 Correct 3 ms 22876 KB Output is correct
6 Correct 4 ms 27228 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 4 ms 33112 KB Output is correct
11 Correct 3 ms 22876 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 2 ms 14684 KB Output is correct
14 Correct 3 ms 26972 KB Output is correct
15 Correct 3 ms 18780 KB Output is correct
16 Correct 4 ms 33116 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 28 ms 93204 KB Output is correct
19 Correct 10 ms 76892 KB Output is correct
20 Correct 15 ms 101596 KB Output is correct
21 Correct 9 ms 80916 KB Output is correct
22 Correct 11 ms 97116 KB Output is correct
23 Correct 9 ms 70568 KB Output is correct
24 Correct 5 ms 43868 KB Output is correct
25 Correct 16 ms 117596 KB Output is correct
26 Correct 15 ms 121692 KB Output is correct
27 Correct 13 ms 109772 KB Output is correct
28 Correct 10 ms 85080 KB Output is correct
29 Correct 10 ms 89180 KB Output is correct
30 Correct 8 ms 70748 KB Output is correct
31 Correct 7 ms 64604 KB Output is correct
32 Correct 9 ms 74972 KB Output is correct
33 Correct 11 ms 101208 KB Output is correct
34 Correct 9 ms 88924 KB Output is correct
35 Correct 11 ms 93348 KB Output is correct
36 Correct 9 ms 80904 KB Output is correct
37 Correct 6 ms 56152 KB Output is correct
38 Correct 7 ms 60320 KB Output is correct
39 Correct 9 ms 76772 KB Output is correct
40 Correct 1 ms 4444 KB Output is correct
41 Correct 4 ms 37468 KB Output is correct
42 Correct 1 ms 8736 KB Output is correct
43 Correct 105 ms 374524 KB Output is correct
44 Correct 43 ms 374272 KB Output is correct
45 Correct 42 ms 374480 KB Output is correct
46 Correct 41 ms 374524 KB Output is correct
47 Correct 43 ms 378196 KB Output is correct
48 Correct 43 ms 377172 KB Output is correct
49 Correct 42 ms 375856 KB Output is correct
50 Correct 45 ms 375888 KB Output is correct
51 Correct 44 ms 377936 KB Output is correct
52 Correct 43 ms 376660 KB Output is correct
53 Correct 39 ms 362580 KB Output is correct
54 Correct 38 ms 349788 KB Output is correct
55 Correct 36 ms 350744 KB Output is correct
56 Correct 49 ms 366676 KB Output is correct
57 Correct 41 ms 366928 KB Output is correct
58 Correct 254 ms 395072 KB Output is correct
59 Correct 235 ms 428112 KB Output is correct
60 Correct 277 ms 467416 KB Output is correct
61 Correct 236 ms 468336 KB Output is correct
62 Correct 52 ms 430776 KB Output is correct
63 Correct 53 ms 433992 KB Output is correct
64 Correct 85 ms 476788 KB Output is correct
65 Correct 131 ms 481188 KB Output is correct
66 Correct 206 ms 472180 KB Output is correct
67 Correct 177 ms 442452 KB Output is correct
68 Correct 202 ms 475288 KB Output is correct
69 Correct 219 ms 473368 KB Output is correct
70 Correct 235 ms 474452 KB Output is correct
71 Correct 188 ms 485096 KB Output is correct
72 Correct 59 ms 442524 KB Output is correct
73 Correct 3 ms 21592 KB Output is correct