oj.uz

Submission #938190

# Submission time Handle Problem Language Result Execution time Memory
938190 2024-03-05T02:03:07 Z LittleOrange Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
60 / 100
 500 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct BIT{
    ll n;
    vector<ll> a;
    BIT(ll N):n(N),a(N+1){}
    void add(ll i, ll x){
        for(;i<=n;i+=i&-i) a[i] += x;
    }
    ll get(ll i){
        ll x = 0;
        for(;i;i-=i&-i) x +=a[i];
        return x;
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    string s;
    cin >> n >> s;
    vector<ll> cnt(3,0);
    vector<ll> a(n);
    vector<vector<ll>> ps(3);
    for(ll i = 0;i<n;i++) {
        a[i] = s[i]=='R'?0:s[i]=='G'?1:2;
        cnt[a[i]]++;
        ps[a[i]].push_back(i+1);
    }
    for(ll i : cnt){
        if (i>(n+1)/2){
            cout << "-1\n";
            return 0;
        }
    }
    vector<vector<ll>> c(3,vector<ll>(n+1,0));
    for(ll i = 0;i<n;i++){
        for(ll j = 0;j<3;j++){
            c[j][i+1] = c[j][i] + (a[i]==j);
        }
    }
    vector<vector<vector<vector<ll>>>> dp(3,vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(n+5,vector<ll>(n+5,1e18))));
    dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
    for(ll i = 0;i<=cnt[0];i++){
        for(ll j = 0;j<=cnt[1];j++){
            for(ll k = 0;k<=cnt[2];k++){
                ll pos = i+j+k;
                if(i>0) dp[0][i][j][k] = min(dp[0][i][j][k],min(dp[1][i-1][j][k],dp[2][i-1][j][k])+max(c[0][ps[0][i-1]]-i,0ll)+max(c[1][ps[0][i-1]]-j,0ll)+max(c[2][ps[0][i-1]]-k,0ll));
                if(j>0) dp[1][i][j][k] = min(dp[1][i][j][k],min(dp[0][i][j-1][k],dp[2][i][j-1][k])+max(c[0][ps[1][j-1]]-i,0ll)+max(c[1][ps[1][j-1]]-j,0ll)+max(c[2][ps[1][j-1]]-k,0ll));
                if(k>0) dp[2][i][j][k] = min(dp[2][i][j][k],min(dp[0][i][j][k-1],dp[1][i][j][k-1])+max(c[0][ps[2][k-1]]-i,0ll)+max(c[1][ps[2][k-1]]-j,0ll)+max(c[2][ps[2][k-1]]-k,0ll));
            }
        }
    }
    ll ans = 1e18;
    for(ll i = 0;i<3;i++) ans = min(ans,dp[i][cnt[0]][cnt[1]][cnt[2]]);
    cout << ans << "\n";
}

Compilation message

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:47:20: warning: unused variable 'pos' [-Wunused-variable]
   47 |                 ll pos = i+j+k;
      |                    ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 708 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 708 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 4 ms 9564 KB Output is correct
20 Correct 4 ms 9564 KB Output is correct
21 Correct 5 ms 9564 KB Output is correct
22 Correct 4 ms 9616 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 4 ms 9416 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 4 ms 9816 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 5 ms 9560 KB Output is correct
30 Correct 5 ms 9564 KB Output is correct
31 Correct 5 ms 9564 KB Output is correct
32 Correct 5 ms 9416 KB Output is correct
33 Correct 0 ms 856 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 4 ms 8796 KB Output is correct
36 Correct 5 ms 9160 KB Output is correct
37 Correct 4 ms 8540 KB Output is correct
38 Correct 4 ms 9564 KB Output is correct
39 Correct 4 ms 9492 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Execution timed out 541 ms 1048576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 708 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 4 ms 9564 KB Output is correct
20 Correct 4 ms 9564 KB Output is correct
21 Correct 5 ms 9564 KB Output is correct
22 Correct 4 ms 9616 KB Output is correct
23 Correct 5 ms 9564 KB Output is correct
24 Correct 4 ms 9416 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 4 ms 9816 KB Output is correct
28 Correct 5 ms 9564 KB Output is correct
29 Correct 5 ms 9560 KB Output is correct
30 Correct 5 ms 9564 KB Output is correct
31 Correct 5 ms 9564 KB Output is correct
32 Correct 5 ms 9416 KB Output is correct
33 Correct 0 ms 856 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 4 ms 8796 KB Output is correct
36 Correct 5 ms 9160 KB Output is correct
37 Correct 4 ms 8540 KB Output is correct
38 Correct 4 ms 9564 KB Output is correct
39 Correct 4 ms 9492 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Execution timed out 541 ms 1048576 KB Time limit exceeded
44 Halted 0 ms 0 KB -