oj.uz

Submission #308324

# Submission time Handle Problem Language Result Execution time Memory
308324 2020-09-30T22:58:55 Z ErdosSzekeres Holding (COCI20_holding) C++14
110 / 110
 121 ms 26488 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 103;
const int MAXK = (MAXN*MAXN)/4 + 3;
int dpL[MAXN][MAXN][MAXK], dpR[MAXN][MAXN][MAXK], n,l,r,k, a[MAXN];
int main(){
    scanf("%d %d %d %d", &n, &l, &r, &k);
    k = min(k, MAXK - 1);
    for(int i=1; i<=n; i++)scanf("%d", &a[i]);
    int orig = 0; for(int i=l; i<=r; i++)orig+=a[i];
    //compute dpL (base case dpL[][][0])
    for(int j=1; j<=k; j++){
        for(int i=1; i<=l-1; i++){
            for(int g=l; g<=r; g++){
                if(j >= g-i)dpL[i][g][j] = max(dpL[i][g][j], dpL[i-1][g-1][j-(g-i)] + a[g] - a[i]);//swap them
                dpL[i][g][j] = max(dpL[i][g][j], dpL[i-1][g][j]);
                dpL[i][g][j] = max(dpL[i][g][j], dpL[i][g-1][j]);
            }
        }
    }
    //compute dpR
    for(int j=1; j<=k; j++){
        for(int i=n; i>=r+1; i--){
            for(int g=r; g>=l; g--){
                if(j >= i-g)dpR[i][g][j] = max(dpR[i][g][j], dpR[i+1][g+1][j-(i-g)] + a[g] - a[i]);//swap them
                dpR[i][g][j] = max(dpR[i][g][j], dpR[i+1][g][j]);
                dpR[i][g][j] = max(dpR[i][g][j], dpR[i][g+1][j]);
            }
        }
    }
    int ans = 0;
    for(int i=l-1; i<=r+1; i++){//position of line
        for(int j=0; j<=k; j++){//money
            //cout<<i<<" "<<j<<" "<<dpL[l-1][i][j] + dpR[r+1][i+1][k-j]<<endl;
            ans = max(ans, dpL[l-1][i][j] + dpR[r+1][i+1][k-j]);
        }
    }
    cout << orig - ans << endl;
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    7 |     scanf("%d %d %d %d", &n, &l, &r, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:9:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     for(int i=1; i<=n; i++)scanf("%d", &a[i]);
      |                            ~~~~~^~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 3 ms 3072 KB Output is correct
11 Correct 3 ms 3200 KB Output is correct
12 Correct 2 ms 1920 KB Output is correct
13 Correct 17 ms 6912 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 3 ms 3072 KB Output is correct
11 Correct 3 ms 3200 KB Output is correct
12 Correct 2 ms 1920 KB Output is correct
13 Correct 17 ms 6912 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 1152 KB Output is correct
16 Correct 2 ms 1664 KB Output is correct
17 Correct 2 ms 1792 KB Output is correct
18 Correct 3 ms 2944 KB Output is correct
19 Correct 16 ms 6912 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 2 ms 2560 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 3 ms 3072 KB Output is correct
11 Correct 3 ms 3200 KB Output is correct
12 Correct 2 ms 1920 KB Output is correct
13 Correct 17 ms 6912 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 1152 KB Output is correct
16 Correct 2 ms 1664 KB Output is correct
17 Correct 2 ms 1792 KB Output is correct
18 Correct 3 ms 2944 KB Output is correct
19 Correct 16 ms 6912 KB Output is correct
20 Correct 9 ms 6400 KB Output is correct
21 Correct 4 ms 3072 KB Output is correct
22 Correct 4 ms 4608 KB Output is correct
23 Correct 6 ms 2944 KB Output is correct
24 Correct 19 ms 12024 KB Output is correct
25 Correct 121 ms 26488 KB Output is correct