Submission #212071

#	Time	Username	Problem	Language	Result	Execution time	Memory
212071		NONAME	Holding (COCI20_holding)	C++17	55 / 110	61 ms	100588 KiB

holding

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 55;
const int K = 10010;
const int oo = 2e9;
int a[N], f[N][N][K], n, l, r, k, ans = oo;

int main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);

    cin >> n >> l >> r >> k;
    
    assert(r == n);
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= n; j++)
            for (int kl = 0; kl <= k; kl++)
                f[i][j][kl] = oo;
        
    f[l][l - 1][k] = 0;
    
    for (int i = l; i <= r; i++)
        f[l][l - 1][k] += a[i];
        
    for (int i = l; i > 0; i--)
        for (int j = l - 1; j <= r; j++)
            for (int ost = 0; ost <= k; ost++){
                if (f[i][j][ost] == oo) continue;
                
                ans = min(ans, f[i][j][ost]);
                
                if (i > 0)
                    f[i - 1][j][ost] = min(f[i - 1][j][ost], f[i][j][ost]);
                
                if (j < r)
                    f[i][j + 1][ost] = min(f[i][j + 1][ost], f[i][j][ost]);
                
                if (i > 0 && j < r) {
                    int n1 = i - 1, n2 = j + 1;
                    f[n1][n2][ost - (n2 - n1)] = min(f[n1][n2][ost - (n2 - n1)], f[i][j][ost] + a[n1] - a[n2]);
                }
            }
    
    cout << ans;
    
    return 0;
}

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