oj.uz

Submission #486918

# Submission time Handle Problem Language Result Execution time Memory
486918 2021-11-13T11:38:34 Z AkiYuu Holding (COCI20_holding) C++17
110 / 110
 20 ms 26016 KB 
#include <bits/stdc++.h>
#define task "GROUP"
#define ll long long
#define ld long double
#define pb(u) emplace_back(u)
#define ffw(i,a,b) for (ll i = a; i <= b; i++)
#define fbw(i,b,a) for (ll i = b; i >= a; i--)
#define adj(v,adj,u) for (auto v : adj[u])
#define rep(i,a) for (auto i : a)
#define reset(a) memset(a, 0, sizeof(a))
#define sz(a) a.size()
#define all(a) a.begin(),a.end()

using namespace std;

inline namespace FastIO {
	const int BSZ = 1<<15;
	char ibuf[BSZ]; int ipos, ilen;
	char nc() { //
		if (ipos == ilen) {
			ipos = 0; ilen = fread(ibuf,1,BSZ,stdin);
			if (!ilen) return EOF;
		}
		return ibuf[ipos++];
	}
	void readstr(string& x) {
		char ch; while (isspace(ch = nc()));
		do { x += ch; } while (!isspace(ch = nc()) && ch != EOF);
	}

	template<class T> void readnum(T& x){
		char ch; int sgn = 1;
		while (!isdigit(ch = nc())) if (ch == '-') sgn *= -1;
		x = ch-'0'; while (isdigit(ch = nc())) x = x*10+(ch-'0');
		x *= sgn;
	}
}

void fastio(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
//	freopen(task".inp", "r", stdin);
//	freopen(task".out", "w", stdout);
}

const int mxn = 1e6 + 5;
typedef pair<ll, ll> ii;
ll a[1000];
ll n , L , R, k;
ll tot = 0;
int dpL[105][105][2600];
int dpR[105][105][2600];

void CredpL(){

    ffw(i,L,R) fbw(j,L-1,1) ffw(c, 0, k){
        int state1 = dpL[i-1][j][c];
        int state2 = dpL[i][j+1][c];
        int state3 = INT_MIN;
        if ( c >= i - j ) state3 = dpL[i-1][j+1][c - (i - j) ] + a[i] - a[j];
        dpL[i][j][c] = max({state1, state2, state3});
    }
}

void CredpR(){

    fbw(i,R,L) ffw(j,R+1,n) ffw(c, 0, k){
        int state1 = dpR[i+1][j][c];
        int state2 = dpR[i][j-1][c];
        int state3 = INT_MIN;
        if ( c >= j - i ) state3 = dpR[i+1][j-1][c - (j - i) ] + a[i] - a[j];
        dpR[i][j][c] = max({state1, state2, state3});
    }
}

void solve(){
    cin >> n >> L >> R >> k;
    k = min(k, n*n/4 + 2);
    ffw(i,1,n) {
        cin >> a[i];
        if ( i >= L && i <= R ) tot += a[i];
    }
    int res = 0;
    CredpL();
    CredpR();
    ffw(i,L-1,R+1){
        ffw(j,0,k){
            res = max(res , dpL[i][1][j] + dpR[i+1][n][k-j] );
        }
    }
    cout << tot - res;
}

int main(){
	fastio();
	solve();
}


//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \|     |// '.
//                 / \|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//

Compilation message

holding.cpp:107:1: warning: multi-line comment [-Wcomment]
  107 | //                 / \|||  :  |||// \
      | ^

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 2380 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 3 ms 4428 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 2380 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 3 ms 4428 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 1 ms 1724 KB Output is correct
18 Correct 2 ms 2764 KB Output is correct
19 Correct 3 ms 4428 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 2380 KB Output is correct
9 Correct 1 ms 2636 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 3 ms 4428 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 2 ms 1612 KB Output is correct
17 Correct 1 ms 1724 KB Output is correct
18 Correct 2 ms 2764 KB Output is correct
19 Correct 3 ms 4428 KB Output is correct
20 Correct 3 ms 6220 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 2 ms 4428 KB Output is correct
23 Correct 2 ms 2252 KB Output is correct
24 Correct 6 ms 12236 KB Output is correct
25 Correct 20 ms 26016 KB Output is correct