제출 #1326403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326403		nathako9n	Holding (COCI20_holding)	C++20	110 / 110	142 ms	208040 KiB

holding

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define f first
#define s second
#define tii tuple<int,int>
using namespace std;
const int K=10005;
ll n,maxk,l,r,ar[105];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>l>>r>>maxk;
    ll sum=0;
    vector<ll> inside, outside;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        if(i>=l&&i<=r)sum+=ar[i];
        if(i >= l && i <= r) inside.push_back(ar[i]);
        else outside.push_back(ar[i]);
    }

    int sz_in = inside.size();
    int sz_out = outside.size();


    vector<vector<vector<ll>>> dp(sz_in + 1, vector<vector<ll>>(sz_out + 1, vector<ll>(maxk + 1, 0)));

    for(int i=1; i <= sz_in; ++i){
        for(int j=1; j <= sz_out; ++j){
            for(int k=0; k <= maxk; ++k){

                dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]);
                int pos_in = l + i - 1;
                int pos_out = (j < l) ? j : (j + (r - l + 1));
                int cost = abs(pos_in - pos_out);

                if(k >= cost && (inside[i-1] - outside[j-1]) > 0){
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-cost] + inside[i-1] - outside[j-1]);
                }
            }
        }
    }

    ll max_gain = 0;
    for(int k=0; k<=maxk; ++k) max_gain = max(max_gain, dp[sz_in][sz_out][k]);

    cout << sum- max_gain;
    return 0;
}
/*

5 2 3 3
21 54 12 2 0


3 2 2 1
1 2 3

*/

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22