oj.uz

Submission #938167

# Submission time Handle Problem Language Result Execution time Memory
938167 2024-03-05T01:33:59 Z LittleOrange Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 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<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])+abs(pos-ps[0][i-1]));
                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])+abs(pos-ps[1][j-1]));
                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])+abs(pos-ps[2][k-1]));
            }
        }
    }
    ll ans = 1e18;
    for(ll i = 0;i<3;i++) ans = min(ans,dp[i][cnt[0]][cnt[1]][cnt[2]]);
    cout << ans/2 << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 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 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 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 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 509 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 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 Incorrect 1 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -