oj.uz

답안 #866346

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
866346 2023-10-26T01:00:48 Z yeediot Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 321 ms 18264 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]=='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

# 결과 실행 시간 메모리 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 420 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 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 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 420 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 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 420 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 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -