Submission #869868

#	Time	Username	Problem	Language	Result	Execution time	Memory
869868		quandlm	Holding (COCI20_holding)	C++14	110 / 110	29 ms	32092 KiB

holding

#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 (stderr)

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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22