oj.uz

Submission #866345

# Submission time Handle Problem Language Result Execution time Memory
866345 2023-10-26T00:59:07 Z yeediot Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 309 ms 18324 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
//Don't open the standings during contests.
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=405;
const int inf=1e12;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s;
    cin>>s;
    s='X'+s;
    vector<int>v(n+1);
    vector<vector<int>>pre(3,vector<int>(n+1,0));
    vector<int>pos[3];
    pos[0].pb(-1);
    pos[1].pb(-1);
    pos[2].pb(-1);
    for(int i=1;i<=n;i++){
        if(s[i]=='Y'){
            v[i]=0;
        }
        else if(s[i]=='G'){
            v[i]=1;
        }
        else {
            v[i]=2;
        }
        pre[v[i]][i]=1;
        for(int j=0;j<3;j++){
            pre[j][i]+=pre[j][i-1];
        }
        pos[v[i]].pb(i);
    }
    vector<vector<vector<int>>>dp(n+1,vector<vector<int>>(n+1,vector<int>(3,1e12)));
    vector<vector<vector<int>>>dp2(n+1,vector<vector<int>>(n+1,vector<int>(3,1e12)));
    dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(i,pre[0][n]);j++){
            for(int k=0;k<=min(i-j,pre[1][n]);k++){
                if(i-j-k<0 or i-j-k>pre[2][n])continue;
                if(j){
                    dp2[j][k][0]=min(max(pos[0][j]-i,0LL)+min(dp[j-1][k][1],dp[j-1][k][2]),inf);
                }
                if(k){
                    dp2[j][k][1]=min(max(pos[1][k]-i,0LL)+min(dp[j][k-1][0],dp[j][k-1][2]),inf);
                }
                int r=i-j-k;
                if(r){
                    dp2[j][k][2]=min(max(pos[2][r]-i,0LL)+min(dp[j][k][0],dp[j][k][1]),inf);
                }
                //for(int h=0;h<3;h++)cout<<i<<' '<<j<<' '<<k<<' '<<r<<' '<<h<<' '<<dp2[j][k][h]<<'\n';
            }
        }
        for(int j=0;j<=n;j++){
            for(int k=0;k<=n;k++){
                for(int g=0;g<3;g++){
                    dp[j][k][g]=dp2[j][k][g];
                    dp2[j][k][g]=inf;
                }
            }
        }
    }
    int ans=1e12;
    for(int i=0;i<3;i++){
        chmin(ans,dp[sz(pos[0])-1][sz(pos[1])-1][i]);
    }
    if(ans>=1e12){
        cout<<-1<<'\n';
    }
    else{
        cout<<ans<<'\n';
    }
}
 /*
 input:
 dp[i][r][g][t]=dp[i-1][r-1][g]
 */

Compilation message

joi2019_ho_t3.cpp: In function 'void setIO(std::string)':
joi2019_ho_t3.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 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 0 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 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 0 ms 348 KB Output is correct
2 Correct 309 ms 18324 KB Output is correct
3 Correct 283 ms 18264 KB Output is correct
4 Correct 295 ms 18124 KB Output is correct
5 Correct 285 ms 18008 KB Output is correct
6 Correct 268 ms 18120 KB Output is correct
7 Correct 309 ms 18036 KB Output is correct
8 Correct 281 ms 18008 KB Output is correct
9 Correct 275 ms 17756 KB Output is correct
10 Correct 306 ms 18140 KB Output is correct
11 Correct 290 ms 18124 KB Output is correct
12 Correct 26 ms 4956 KB Output is correct
13 Correct 54 ms 8536 KB Output is correct
14 Correct 114 ms 12380 KB Output is correct
15 Correct 306 ms 18260 KB Output is correct
16 Correct 279 ms 18120 KB Output is correct

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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -