oj.uz

Submission #686657

# Submission time Handle Problem Language Result Execution time Memory
686657 2023-01-25T17:17:58 Z Farhan_HY Holding (COCI20_holding) C++14
55 / 110
 29 ms 61900 KB 
#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

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 61780 KB Output is correct
2 Correct 23 ms 61844 KB Output is correct
3 Correct 22 ms 61816 KB Output is correct
4 Correct 23 ms 61780 KB Output is correct
5 Correct 29 ms 61772 KB Output is correct
6 Correct 22 ms 61780 KB Output is correct
7 Correct 22 ms 61824 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 61780 KB Output is correct
2 Correct 23 ms 61844 KB Output is correct
3 Correct 22 ms 61816 KB Output is correct
4 Correct 23 ms 61780 KB Output is correct
5 Correct 29 ms 61772 KB Output is correct
6 Correct 22 ms 61780 KB Output is correct
7 Correct 22 ms 61824 KB Output is correct
8 Correct 25 ms 61848 KB Output is correct
9 Correct 24 ms 61860 KB Output is correct
10 Correct 24 ms 61804 KB Output is correct
11 Correct 23 ms 61780 KB Output is correct
12 Correct 24 ms 61900 KB Output is correct
13 Correct 24 ms 61868 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 61780 KB Output is correct
2 Correct 23 ms 61844 KB Output is correct
3 Correct 22 ms 61816 KB Output is correct
4 Correct 23 ms 61780 KB Output is correct
5 Correct 29 ms 61772 KB Output is correct
6 Correct 22 ms 61780 KB Output is correct
7 Correct 22 ms 61824 KB Output is correct
8 Correct 25 ms 61848 KB Output is correct
9 Correct 24 ms 61860 KB Output is correct
10 Correct 24 ms 61804 KB Output is correct
11 Correct 23 ms 61780 KB Output is correct
12 Correct 24 ms 61900 KB Output is correct
13 Correct 24 ms 61868 KB Output is correct
14 Correct 24 ms 61772 KB Output is correct
15 Incorrect 24 ms 61772 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 61780 KB Output is correct
2 Correct 23 ms 61844 KB Output is correct
3 Correct 22 ms 61816 KB Output is correct
4 Correct 23 ms 61780 KB Output is correct
5 Correct 29 ms 61772 KB Output is correct
6 Correct 22 ms 61780 KB Output is correct
7 Correct 22 ms 61824 KB Output is correct
8 Correct 25 ms 61848 KB Output is correct
9 Correct 24 ms 61860 KB Output is correct
10 Correct 24 ms 61804 KB Output is correct
11 Correct 23 ms 61780 KB Output is correct
12 Correct 24 ms 61900 KB Output is correct
13 Correct 24 ms 61868 KB Output is correct
14 Correct 24 ms 61772 KB Output is correct
15 Incorrect 24 ms 61772 KB Output isn't correct
16 Halted 0 ms 0 KB -