提出 #76220292

---

ソースコード 拡げる

//#define _GLIBCXX_DEBUG
//提出の際、1行目はコメントアウトすること
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(a,b) for(ll a=0;a<b;a++)
#define rrep(a,b) for(ll a=b-1;a>=0;a--)
const long double pai=3.14159265358979323;
using Pair = pair<ll,ll>;
#define MOD 998244353
#define INF 1000000000000000000
#define MINF -1000000000000000000
using vll = vector<ll>;
#include <atcoder/all>
using namespace atcoder;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N,K;
    cin>>N>>K;
    vector<Pair> A(N);
    rep(i,N){
        cin>>A[i].first>>A[i].second;
    }

    vector<vll> dp(N+1,vll(K+1,-INF));
    dp[0][0]=0;

    rep(i,N){
        rep(j,K+1){
            if(dp[i][j]==-INF){continue;}
            if(A[i].first==1){
                dp[i+1][j]=max(dp[i][j],dp[i+1][j]);//断った場合
                if(j!=K){dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+A[i].second);}
            }
            else{
                if(j==0){
                    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+A[i].second);
                }

                dp[i+1][j]=max(dp[i][j],dp[i+1][j]);//断った場合
                if(j!=0){dp[i+1][j-1]=max(dp[i+1][j-1],dp[i][j]+A[i].second);}
            }
        }
    }

    cout<<dp[N][0]<<endl;

}

提出情報

ジャッジ結果