oj.uz

Submission #235493

# Submission time Handle Problem Language Result Execution time Memory
235493 2020-05-28T11:22:45 Z doowey Holding (COCI20_holding) C++14
88 / 110
 187 ms 148216 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 + M] == inf) continue;
      for(int y = 0; x + y <= k; y ++ ){
        if(dpR[i + 1][0][y + M] == inf) continue;
        upd(ans, dpL[i][0][x + M] + dpR[i + 1][0][y + M]);
      }
    }
  }
  cout << ans << "\n";
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5504 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 4992 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5504 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 4992 KB Output is correct
8 Correct 52 ms 64816 KB Output is correct
9 Correct 55 ms 64760 KB Output is correct
10 Correct 56 ms 64760 KB Output is correct
11 Correct 55 ms 64640 KB Output is correct
12 Correct 56 ms 64768 KB Output is correct
13 Correct 187 ms 64632 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5504 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 4992 KB Output is correct
8 Correct 52 ms 64816 KB Output is correct
9 Correct 55 ms 64760 KB Output is correct
10 Correct 56 ms 64760 KB Output is correct
11 Correct 55 ms 64640 KB Output is correct
12 Correct 56 ms 64768 KB Output is correct
13 Correct 187 ms 64632 KB Output is correct
14 Correct 49 ms 64760 KB Output is correct
15 Correct 51 ms 64768 KB Output is correct
16 Correct 48 ms 64760 KB Output is correct
17 Correct 48 ms 64760 KB Output is correct
18 Correct 54 ms 64632 KB Output is correct
19 Correct 186 ms 64888 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1408 KB Output is correct
2 Correct 8 ms 5504 KB Output is correct
3 Correct 8 ms 5504 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 4992 KB Output is correct
8 Correct 52 ms 64816 KB Output is correct
9 Correct 55 ms 64760 KB Output is correct
10 Correct 56 ms 64760 KB Output is correct
11 Correct 55 ms 64640 KB Output is correct
12 Correct 56 ms 64768 KB Output is correct
13 Correct 187 ms 64632 KB Output is correct
14 Correct 49 ms 64760 KB Output is correct
15 Correct 51 ms 64768 KB Output is correct
16 Correct 48 ms 64760 KB Output is correct
17 Correct 48 ms 64760 KB Output is correct
18 Correct 54 ms 64632 KB Output is correct
19 Correct 186 ms 64888 KB Output is correct
20 Runtime error 133 ms 148216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -