oj.uz

Submission #920268

# Submission time Handle Problem Language Result Execution time Memory
920268 2024-02-02T11:33:09 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 11612 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int inf = 1e9,N = 3e5+1;

inline void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (auto& it : s) {
        if (it == 'R') it = 'A';
        else if (it == 'G') it = 'B';
        else it = 'C';
    }
    int dp[n+1][n+1][3][3];
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            for (int k=0;k<3;k++) {
                for (int k2=0;k2<3;k2++) dp[i][j][k][k2] = inf;
            }
        }
    }
    for (int i=1;i<=n;i++) dp[i][i][s[i-1]-'A'][s[i-1]-'A'] = 0;
    for (int L=n;L>=1;L--) {
        for (int R = L+1;R<=n;R++) {
            for (int a = 0;a<3;a++) {
                for (int b=0;b < 3;b++) {
                    for (int x = L;x<R;x++) {
                        for (int i=0;i<3;i++) {
                            for (int j=0;j<3;j++) {
                                if (i == j) continue;
    dp[L][R][a][b]=min(dp[L][R][a][b],dp[L][x][a][i]+dp[x+1][R][j][b]);
    dp[L][R][a][b]=min(dp[L][R][a][b],dp[L][x][i][b]+dp[x+1][R][a][j]+(x-L+1)*(R-x));
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = inf;
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) ans = min(ans,dp[1][n][i][j]);
    cout << ((ans==inf)?-1:ans) << '\n';
}   
    
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 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 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -