Submission #866346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
866346	2023-10-26T01:00:48 Z	yeediot	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	321 ms	18264 KB

joi2019_ho_t3

#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]=='R'){
            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	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	420 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Incorrect	348 KB	Output isn't correct
12	Halted	0 KB	-

Subtask #2
0 / 55.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	420 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Incorrect	348 KB	Output isn't correct
12	Halted	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	301 ms	18120 KB	Output is correct
3	Correct	289 ms	18256 KB	Output is correct
4	Correct	281 ms	18112 KB	Output is correct
5	Correct	274 ms	18012 KB	Output is correct
6	Correct	321 ms	18008 KB	Output is correct
7	Correct	291 ms	18264 KB	Output is correct
8	Correct	290 ms	18040 KB	Output is correct
9	Correct	288 ms	17948 KB	Output is correct
10	Correct	290 ms	18012 KB	Output is correct
11	Correct	319 ms	18012 KB	Output is correct
12	Correct	27 ms	4952 KB	Output is correct
13	Correct	59 ms	8540 KB	Output is correct
14	Correct	124 ms	12380 KB	Output is correct
15	Correct	294 ms	18008 KB	Output is correct
16	Correct	282 ms	18012 KB	Output is correct

Subtask #4
0 / 25.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	420 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	348 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	348 KB	Output is correct
11	Incorrect	348 KB	Output isn't correct
12	Halted	0 KB	-

Submission #866346

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 55.0

Subtask #3 15.0 / 15.0

Subtask #4 0 / 25.0

Subtask #1
0 / 5.0

Subtask #2
0 / 55.0

Subtask #3
15.0 / 15.0

Subtask #4
0 / 25.0