Submission #686657

#	Time	Username	Problem	Language	Result	Execution time	Memory
686657		Farhan_HY	Holding (COCI20_holding)	C++14	55 / 110	29 ms	61900 KiB

holding

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = 1e6 + 5;
const int M = 1e3 + 3;
const int inf = 1e18;
const int mod = 1e9 + 7;
int n, l, r, k, a[N], dp[55][55][2600];

int Rec(int i, int cnt, int sum) {
    if (i > n) {
        if (sum - 1300 > k || cnt != 0) return inf;
        return 0;
    }
    int &ret = dp[i][cnt][sum];
    if (ret != -1) return ret;
    if (i < l)
        ret = min(Rec(i + 1, cnt + 1, sum - i) + a[i], Rec(i + 1, cnt, sum));
    else {
        ret = Rec(i + 1, cnt, sum);
        if (cnt) 
            ret = min(ret, Rec(i + 1, cnt - 1, sum + i) - a[i]);
    }
    return ret;
}

main() {
    IOS
    cin >> n >> l >> r >> k;
    int sum = 0;
    for(int i = 1; i <= n; i++) cin >> a[i], sum += a[i] * (i >= l && i <= r);
    memset(dp, -1, sizeof dp);
    cout << Rec(1, 0, 1300) + sum;
}

Compilation message (stderr)

holding.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main() {
      | ^~~~

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