oj.uz

Submission #1075686

# Submission time Handle Problem Language Result Execution time Memory
1075686 2024-08-26T08:36:11 Z dosts Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 3 ms 1412 KB 
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e7;
const int N = 5001;

void solve() { 
    int n;
    cin >> n;
    string s;
    cin >> s;
    vi as,bs,cs;
    as.push_back(0),bs.push_back(0),cs.push_back(0);
    for (int i=0;i<n;i++) {
        if (s[i] == 'R') as.push_back(i+1);
        else if (s[i] == 'G') bs.push_back(i+1);
        else cs.push_back(i+1);
    }
    auto cost = [&](int a,int b,int c,int p) {
        int pos;
        if (p == 0) pos = as[a];
        else if (p == 1) pos = bs[b];
        else pos = cs[c];
        int curpos = a+b+c;
        //cout << pos sp curpos << endl;
        if (pos < curpos) return 0;
        return pos-curpos;
    };
    int sa = as.size(),sb = bs.size(),sc = cs.size();
    int dp[sa+1][sb+1][sc+1][3];
    for (int i=0;i<=sa;i++) for (int ii=0;ii<=sb;ii++) for (int iii=0;iii<=sc;iii++) for (int p=0;p<3;p++) dp[i][ii][iii][p] = inf;
    dp[1][0][0][0] = as[1]-1;
    dp[0][1][0][1] = bs[1]-1;
    dp[0][0][1][2] = cs[1]-1;
    for (int a=0;a<=sa-1;a++) {
        for (int b=0;b<=sb-1;b++) {
            for (int c=0;c<=sc-1;c++) {
                if ((a+b+c) <= 1) continue;
                vi dims{a,b,c};
                for (int p=0;p<3;p++) {
                    dp[a][b][c][p] = inf;
                    if (!dims[p]) continue;
                    dims[p]--;
                    int costy = cost(a,b,c,p);
                    for (int pp=0;pp<3;pp++) {
                        if (p == pp) continue;
                        if (dp[dims[0]][dims[1]][dims[2]][pp] >= inf) continue;
                        dp[a][b][c][p] = min(dp[a][b][c][p],
                        dp[dims[0]][dims[1]][dims[2]][pp]+costy);
                    }
                    dims[p]++;
                }
            }
        } 
    }
    int ans = min({dp[sa-1][sb-1][sc-1][0],
                 dp[sa-1][sb-1][sc-1][1],      
                 dp[sa-1][sb-1][sc-1][2]});
    if (ans >= inf) cout << -1 << endl;
    else cout << ans << endl;
}
 
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 364 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 1 ms 348 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 344 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 364 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 1 ms 348 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 348 KB Output is correct
2 Correct 2 ms 1372 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 2 ms 1412 KB Output is correct
5 Correct 2 ms 1372 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 2 ms 1224 KB Output is correct
8 Correct 3 ms 1368 KB Output is correct
9 Correct 2 ms 1404 KB Output is correct
10 Correct 2 ms 1368 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 2 ms 1372 KB Output is correct
16 Correct 2 ms 1372 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 364 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 1 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -