Submission #442679

#	Time	Username	Problem	Language	Result	Execution time	Memory
442679		Saynaa	Holding (COCI20_holding)	C++14	110 / 110	82 ms	50504 KiB

holding

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100 + 2, MAXK = 5e3 + 2;
int n, k, l, r, a[MAXN], sum;
int dp[MAXN][MAXN][MAXK], L[MAXN][MAXK];
int ans;


int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> l >> r >> k;
	k = min(k, n*n/2);
	for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = l; i <= r; i ++){
    	sum += a[i];
    	for(int j = l - 1; j > 0; j --){
    		for(int kp = 0; kp <= k; kp ++){
    			dp[i][j][kp] = max(dp[i][j][kp], dp[i - 1][j][kp]);
    			dp[i][j][kp] = max(dp[i][j][kp], dp[i][j + 1][kp]);
    			if( kp >= i - j)
    				dp[i][j][kp] = max(dp[i][j][kp], dp[i -1 ][j + 1][kp - (i - j)] + a[i] - a[j]);
			}
		}
	}
	for(int i = l - 1; i <= r; i ++)
		for(int j = 0; j <= k; j ++)
			L[i][j] = dp[i][1][j];
   
       for(int i = l; i <= r; i ++)
    	for(int j = l - 1; j > 0; j --)
    		for(int kp = 0; kp <= k; kp ++)
    			dp[i][j][kp] = 0;
			
	for(int i = r; i >= l; i --){
		for(int j = r + 1; j <= n; j ++){
			for(int kp = 0; kp <= k; kp ++){
				dp[i][j][kp] = max(dp[i][j][kp], dp[i + 1][j][kp]);
				dp[i][j][kp] = max(dp[i][j][kp], dp[i][j - 1][kp]);
				if( kp >= j - i)
					dp[i][j][kp] = max(dp[i][j][kp], dp[i + 1][j - 1][kp - (j - i)] + a[i] - a[j]);
			}
		}
      
	}
	for(int i = l - 1; i <= r; i ++)
		for(int j = 0; j <= k; j ++)
			ans = max(ans, L[i][j] + dp[i + 1][n][k- j]);
	cout << sum - ans << endl;


	
	return 0;
}

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:30:8: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   30 |        for(int i = l; i <= r; i ++)
      |        ^~~
holding.cpp:35:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   35 |  for(int i = r; i >= l; i --){
      |  ^~~

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 22 / 22