oj.uz

Submission #198509

# Submission time Handle Problem Language Result Execution time Memory
198509 2020-01-26T12:34:44 Z quocnguyen1012 Holding (COCI20_holding) C++14
22 / 110
 8 ms 4216 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

template<class T> inline bool chkmin(T & a, const T & val) {return val < a ? a = val, 1 : 0;}
template<class T> inline bool chkmax(T & a, const T & val) {return a < val ? a = val, 1 : 0;}

const int maxn = 105;

int fl[maxn][maxn][2505], fr[maxn][maxn][2505];
int N, L, R, K, a[maxn];
int sum[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N >> L >> R >> K;
  K = min(K, N * N / 4);
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
  }
  for (int i = 1; i < L; ++i){
    for (int j = L; j <= R; ++j){
      for (int cost = 0; cost <= K; ++cost){
        chkmin(fl[i][j][cost], fl[i - 1][j][cost]);
        chkmin(fr[i][j][cost], fl[i][j - 1][cost]);
        if (j - i <= cost) chkmin(fl[i][j][cost], fl[i - 1][j - 1][cost - (j - i)] - a[j] + a[i]);
      }
    }
  }
  for (int i = N; i > R; --i){
    for (int j = R; j >= L; --j){
      for (int cost = 0; cost <= K; ++cost){
        chkmin(fr[i][j][cost], fr[i + 1][j][cost]);
        chkmin(fr[i][j][cost], fr[i][j + 1][cost]);
        if (i - j <= cost) chkmin(fr[i][j][cost], fr[i + 1][j + 1][cost - (i - j)] - a[j] + a[i]);
      }
    }
  }
  int ret = 1e9;
  for (int i = L - 1; i <= R; ++i){
    for (int cost = 0; cost <= K; ++cost){
      chkmin(ret, fl[L - 1][i][cost] + fr[R + 1][i + 1][K - cost]);
    }
  }
  cout << ret + sum[R] - sum[L - 1] << '\n';
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
holding.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Incorrect 8 ms 4216 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Incorrect 8 ms 4216 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 632 KB Output is correct
8 Incorrect 8 ms 4216 KB Output isn't correct
9 Halted 0 ms 0 KB -