結果

問題 No.1606 Stuffed Animals Keeper
ユーザー 沙耶花
提出日時 2021-07-16 21:47:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 61 ms / 3,000 ms
コード長 966 bytes
コンパイル時間 3,778 ms
コンパイル使用メモリ 250,804 KB
最終ジャッジ日時 2025-01-23 01:38:09
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000001
int main(){
    
    int N;
    cin>>N;
    
    vector<int> A(N);
    rep(i,N){
        cin>>A[i];
    }
    
    vector<int> l,r;
    rep(i,N){
        l.push_back(i);
        for(int j=i;j<N;j++){
            if(A[j]==2){
                r.push_back(j);
                break;
            }
        }
        if(l.size()!=r.size()){
            r.push_back(N);
        }
        i = r.back();
    }
    
    int cnt = 0;
    rep(i,N){
        if(A[i]==1){
            cnt++;
        }
    }
    
    vector<int> cost(l.size(),0);
    
    rep(i,l.size()){
        for(int j=l[i];j<r[i];j++){
            if(A[j]==0){
                cost[i]++;
            }
        }
    }
    
    vector dp(N+1,Inf);
    dp[0] = 0;
    
    rep(i,l.size()){
        vector ndp(N+1,Inf);
        rep(j,N+1){
            ndp[j] = min(ndp[j],dp[j]);
            int nj = j + (r[i] - l[i]);
            if(nj>N)continue;
            ndp[nj] = min(ndp[nj],dp[j] + cost[i]);
        }
        swap(dp,ndp);
    }
    
    int ans = dp[cnt];
    if(ans==Inf)ans = -1;
    
    cout<<ans<<endl;
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0