oj.uz

Submission #212100

# Submission time Handle Problem Language Result Execution time Memory
212100 2020-03-22T09:18:59 Z NONAME Holding (COCI20_holding) C++17
110 / 110
 58 ms 12536 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
const int K = 10010;
const int oo = 2e9;
int a[N], f[2][N][K], n, l, r, k, ans[N][K], answ[N][K], res = oo;

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

    cin >> n >> l >> r >> k;
        
    for (int i = 1; i <= n; i++)
        cin >> a[i];
        
    for (int i = 0; i < n + 2; i++)
        fill(ans[i], ans[i] + k + 1, oo);
        
    for (int j = l - 1; j <= r; j++)
        for (int ost = 0; ost <= k; ost++)
            f[0][j][ost] = oo;
        
    f[0][l - 1][k] = 0;
    
    for (int i = l; i <= r; i++)
        f[0][l - 1][k] += a[i];
        
    int sum = f[0][l - 1][k], it = 0;
        
    for (int i = l; i > 0; i--, it ^= 1) {
            
        for (int j = l - 1; j <= r; j++)
            for (int ost = 0; ost <= k; ost++)
                f[it ^ 1][j][ost] = oo;
            
        for (int j = l - 1; j <= r; j++)
            for (int ost = 0; ost <= k; ost++){
                if (f[it][j][ost] == oo) continue;
                
                ans[j][ost] = min(ans[j][ost], f[it][j][ost]);
                
                if (i > 0)
                    f[it ^ 1][j][ost] = min(f[it ^ 1][j][ost], f[it][j][ost]);
                
                if (j < r)
                    f[it][j + 1][ost] = min(f[it][j + 1][ost], f[it][j][ost]);
                
                if (i > 0 && j < r) {
                    int n1 = i - 1, n2 = j + 1;
                    f[it ^ 1][n2][ost - (n2 - n1)] = min(f[it ^ 1][n2][ost - (n2 - n1)], f[it][j][ost] + a[n1] - a[n2]);
                }
            }
    }
    
    for (int ost = k; ost >= 0; ost--) 
        for (int i = l - 1; i <= r; i++){
            if (i >= l)
                ans[i][ost] = min(ans[i][ost], ans[i - 1][ost]);
            
            if (ost >= 0)
                ans[i][ost - 1] = min(ans[i][ost - 1], ans[i][ost]);
        }
    
    // right side
    
    for (int i = 0; i < n + 2; i++)
        fill(answ[i], answ[i] + k + 1, oo);
    
    for (int j = r + 1; j >= l; j--)
        for (int ost = 0; ost <= k; ost++)
            f[0][j][ost] = oo;
        
    it = 0;
    f[0][r + 1][k] = 0;
    
    for (int i = l; i <= r; i++)
        f[0][r + 1][k] += a[i];
        
    for (int i = r; i <= n; i++, it ^= 1){
            
        for (int j = r + 1; j >= l; j--)
            for (int ost = 0; ost <= k; ost++)
                f[it ^ 1][j][ost] = oo;
            
        for (int j = r + 1; j >= l; j--)
            for (int ost = 0; ost <= k; ost++){
                if (f[it][j][ost] == oo) continue;
                
                answ[j][ost] = min(answ[j][ost], f[it][j][ost]);
                
                if (i < n)
                    f[it ^ 1][j][ost] = min(f[it ^ 1][j][ost], f[it][j][ost]);
                
                if (j > l)
                    f[it][j - 1][ost] = min(f[it][j - 1][ost], f[it][j][ost]);
                
                if (i < n && j > l) {
                    int n1 = i + 1, n2 = j - 1;
                    f[it ^ 1][n2][ost - (n1 - n2)] = min(f[it ^ 1][n2][ost - (n1 - n2)], f[it][j][ost] + a[n1] - a[n2]);
                }
            }
    }
    
    for (int i = r + 1; i >= l; i--)
        for (int ost = 0; ost <= k; ost++) {
            if (i <= r)
                answ[i][ost] = min(answ[i][ost], answ[i + 1][ost]);
            
            int opp = k - ost;
            
            if (ans[i - 1][opp] < oo && answ[i][ost] < oo) 
                res = min(res, ans[i - 1][opp] + answ[i][ost]);
        }
        
    cout << res - sum;
    
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 7 ms 2176 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 7 ms 2176 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 19 ms 6656 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 7 ms 2176 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 19 ms 6656 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 896 KB Output is correct
16 Correct 5 ms 896 KB Output is correct
17 Correct 5 ms 896 KB Output is correct
18 Correct 5 ms 1024 KB Output is correct
19 Correct 19 ms 6656 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 7 ms 2176 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 5 ms 1152 KB Output is correct
13 Correct 19 ms 6656 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 896 KB Output is correct
16 Correct 5 ms 896 KB Output is correct
17 Correct 5 ms 896 KB Output is correct
18 Correct 5 ms 1024 KB Output is correct
19 Correct 19 ms 6656 KB Output is correct
20 Correct 7 ms 1664 KB Output is correct
21 Correct 6 ms 1792 KB Output is correct
22 Correct 5 ms 1280 KB Output is correct
23 Correct 8 ms 4352 KB Output is correct
24 Correct 10 ms 2176 KB Output is correct
25 Correct 58 ms 12536 KB Output is correct