oj.uz

Submission #212071

# Submission time Handle Problem Language Result Execution time Memory
212071 2020-03-22T08:28:35 Z NONAME Holding (COCI20_holding) C++17
55 / 110
 61 ms 100588 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 8 ms 6528 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 8 ms 6528 KB Output is correct
8 Correct 10 ms 11392 KB Output is correct
9 Correct 9 ms 11648 KB Output is correct
10 Correct 10 ms 11776 KB Output is correct
11 Correct 11 ms 12800 KB Output is correct
12 Correct 9 ms 11904 KB Output is correct
13 Correct 61 ms 100588 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 8 ms 6528 KB Output is correct
8 Correct 10 ms 11392 KB Output is correct
9 Correct 9 ms 11648 KB Output is correct
10 Correct 10 ms 11776 KB Output is correct
11 Correct 11 ms 12800 KB Output is correct
12 Correct 9 ms 11904 KB Output is correct
13 Correct 61 ms 100588 KB Output is correct
14 Runtime error 12 ms 544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 5 ms 1152 KB Output is correct
7 Correct 8 ms 6528 KB Output is correct
8 Correct 10 ms 11392 KB Output is correct
9 Correct 9 ms 11648 KB Output is correct
10 Correct 10 ms 11776 KB Output is correct
11 Correct 11 ms 12800 KB Output is correct
12 Correct 9 ms 11904 KB Output is correct
13 Correct 61 ms 100588 KB Output is correct
14 Runtime error 12 ms 544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -