oj.uz

Submission #869868

# Submission time Handle Problem Language Result Execution time Memory
869868 2023-11-06T03:14:47 Z quandlm Holding (COCI20_holding) C++14
110 / 110
 29 ms 32092 KB 
#include <bits/stdc++.h>
#define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, a, b) for (int i = (a); i >= (b); --i)
#define pi pair<int,int>
#define ple tuple<int,int,int>
#define fi first
#define se second
#define ii make_pair
#define isz(a) ((int)a.size())
#define ALL(a) a.begin(), a.end()

using namespace std;

const int N = 1e6 + 10;
const int mx = 3000;

int n, l, r, K;
int a[N], sum = 0;
int pref[105][105][3005];
int suf[105][105][3005];


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

void maximize (int &a, int b) {
     a = max(a, b);
}

int main () {
    file("debt");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> l >> r >> K;
    K=min(K, mx);
    FOR(i,1,n) cin >> a[i];
    FOR(i,l,r) sum+=a[i];
    for(int i=l; i<=r; ++i) {
        for(int j=1; j<=l-1; ++j) {
            for(int k=0;k<=K;++k) {
                maximize(pref[i][j][k], pref[i-1][j][k]);
                maximize(pref[i][j][k], pref[i][j-1][k]);
                int cost=i-j;
                if (k >= cost) {
                    maximize(pref[i][j][k], pref[i-1][j-1][k-cost]+a[i]-a[j]);
                }
            }
        }
    }

    for(int i=r; i>=l;--i) {
        for(int j=n; j>=r+1; --j) {
             for (int k=0;k<=K;++k) {
                  maximize(suf[i][j][k], suf[i+1][j][k]);
                  maximize(suf[i][j][k], suf[i][j+1][k]);
                  int cost=j-i;
                  if(k >= cost) {
                     maximize(suf[i][j][k], suf[i+1][j+1][k-cost]+a[i]-a[j]);
                  }
             }
        }
    }

    int res = 0;

    for (int i = l-1; i <= r; ++i) {
         for (int j = 0; j <= K; ++j) {
              maximize(res, pref[i][l-1][j] + suf[i+1][r+1][K-j]);
         }
    }

    cout << sum - res << '\n';
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:2:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:34:5: note: in expansion of macro 'file'
   34 |     file("debt");
      |     ^~~~
holding.cpp:2:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    2 | #define file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:34:5: note: in expansion of macro 'file'
   34 |     file("debt");
      |     ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3672 KB Output is correct
17 Correct 1 ms 3928 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 8 ms 9820 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2908 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4952 KB Output is correct
10 Correct 3 ms 5212 KB Output is correct
11 Correct 2 ms 5468 KB Output is correct
12 Correct 1 ms 4188 KB Output is correct
13 Correct 8 ms 9820 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 1 ms 3672 KB Output is correct
17 Correct 1 ms 3928 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 8 ms 9820 KB Output is correct
20 Correct 4 ms 8284 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Correct 2 ms 6492 KB Output is correct
23 Correct 3 ms 4700 KB Output is correct
24 Correct 7 ms 14428 KB Output is correct
25 Correct 29 ms 32092 KB Output is correct