oj.uz

Submission #235491

# Submission time Handle Problem Language Result Execution time Memory
235491 2020-05-28T11:13:49 Z doowey Holding (COCI20_holding) C++14
55 / 110
 158 ms 64768 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 55;
const int S = N * (N + 1);
const int M = S/2;
const int inf = (int)1e9;

int dpL[N][N][S]; // pick i items, indice sum j
int dpR[N][N][S];
int a[N];

void upd(int &a, int b){  
  a = min(a, b);
}

int main(){
  fastIO;
  int n, l, r, k;
  cin >> n >> l >> r >> k;
  for(int q = 0; q <= n + 1; q ++ ){
    for(int d = 0; d <= n; d ++ ){
      for(int s = 0; s < S; s ++ ){
        dpL[q][d][s] = inf;
        dpR[q][d][s] = inf;
      }
    }
  }
  dpL[0][0][M]=0;
  int ans = 0;
  for(int i = 1; i <= n; i ++ ){
    cin >> a[i];
    if(i >= l && i <= r) ans += a[i];
  }
  for(int i = 1; i <= r; i ++ ){
    for(int j = 0 ; j <= n ; j ++ ){
      for(int x = 0; x < S ; x ++ ){
        if(i < l){
          if(dpL[i-1][j][x] == inf) continue;
          upd(dpL[i][j + 1][x - i], dpL[i-1][j][x] + a[i]);
          upd(dpL[i][j][x], dpL[i-1][j][x]);
        }
        else{
          if(dpL[i-1][j][x] == inf) continue;
          if(j) upd(dpL[i][j - 1][x + i], dpL[i-1][j][x]);
          upd(dpL[i][j][x], dpL[i-1][j][x] + a[i]);
        }
      }
    }
  }
  for(int x = 0; x <= k ; x ++ ){
    upd(ans, dpL[r][0][x + M]);
  }
  dpR[n + 1][0][M]=0;
  for(int i = n; i >= l ; i -- ){
    for(int j = 0 ; j <= n; j ++ ){
      for(int x = 0; x < S; x ++ ){
        if(dpR[i + 1][j][x] == inf) continue;
        if(i > r){
          upd(dpR[i][j + 1][x + i], dpR[i + 1][j][x] + a[i]);
          upd(dpR[i][j][x], dpR[i + 1][j][x]);
        }
        else{
          if(j) upd(dpR[i][j - 1][x - i], dpR[i + 1][j][x]);
          upd(dpR[i][j][x], dpR[i + 1][j][x] + a[i]);
        }
      }
    }
  }
  for(int x = 0; x <= k ; x ++ ){
    upd(ans, dpR[l][0][x + M]);
  }
  for(int i = l ; i + 1 <= r; i ++ ){
    for(int x = 0; x <= k; x ++ ){
      if(dpL[i][0][x] == inf) continue;
      for(int y = 0; x + y <= k; y ++ ){
        if(dpR[i + 1][0][y] == inf) continue;
        upd(ans, dpL[i][0][x] + dpR[i + 1][0][y]);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 10 ms 4864 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 10 ms 4864 KB Output is correct
8 Correct 50 ms 64760 KB Output is correct
9 Correct 52 ms 64768 KB Output is correct
10 Correct 52 ms 64760 KB Output is correct
11 Correct 52 ms 64760 KB Output is correct
12 Correct 53 ms 64760 KB Output is correct
13 Correct 158 ms 64768 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 10 ms 4864 KB Output is correct
8 Correct 50 ms 64760 KB Output is correct
9 Correct 52 ms 64768 KB Output is correct
10 Correct 52 ms 64760 KB Output is correct
11 Correct 52 ms 64760 KB Output is correct
12 Correct 53 ms 64760 KB Output is correct
13 Correct 158 ms 64768 KB Output is correct
14 Correct 47 ms 64768 KB Output is correct
15 Correct 48 ms 64760 KB Output is correct
16 Incorrect 46 ms 64760 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 8 ms 5504 KB Output is correct
5 Correct 8 ms 5504 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 10 ms 4864 KB Output is correct
8 Correct 50 ms 64760 KB Output is correct
9 Correct 52 ms 64768 KB Output is correct
10 Correct 52 ms 64760 KB Output is correct
11 Correct 52 ms 64760 KB Output is correct
12 Correct 53 ms 64760 KB Output is correct
13 Correct 158 ms 64768 KB Output is correct
14 Correct 47 ms 64768 KB Output is correct
15 Correct 48 ms 64760 KB Output is correct
16 Incorrect 46 ms 64760 KB Output isn't correct
17 Halted 0 ms 0 KB -