답안 #442679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442679	2021-07-08T14:49:26 Z	Saynaa	Holding (COCI20_holding)	C++14	110 / 110	82 ms	50504 KB

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

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.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	448 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct

Subtask #2

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	448 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	2 ms	2508 KB	Output is correct
9	Correct	2 ms	2752 KB	Output is correct
10	Correct	2 ms	3244 KB	Output is correct
11	Correct	3 ms	3404 KB	Output is correct
12	Correct	2 ms	2252 KB	Output is correct
13	Correct	6 ms	6220 KB	Output is correct

Subtask #3

33.0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	448 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	2 ms	2508 KB	Output is correct
9	Correct	2 ms	2752 KB	Output is correct
10	Correct	2 ms	3244 KB	Output is correct
11	Correct	3 ms	3404 KB	Output is correct
12	Correct	2 ms	2252 KB	Output is correct
13	Correct	6 ms	6220 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	2 ms	1740 KB	Output is correct
18	Correct	3 ms	2892 KB	Output is correct
19	Correct	6 ms	6212 KB	Output is correct

Subtask #4

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	448 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	1 ms	448 KB	Output is correct
7	Correct	1 ms	460 KB	Output is correct
8	Correct	2 ms	2508 KB	Output is correct
9	Correct	2 ms	2752 KB	Output is correct
10	Correct	2 ms	3244 KB	Output is correct
11	Correct	3 ms	3404 KB	Output is correct
12	Correct	2 ms	2252 KB	Output is correct
13	Correct	6 ms	6220 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	2 ms	1740 KB	Output is correct
18	Correct	3 ms	2892 KB	Output is correct
19	Correct	6 ms	6212 KB	Output is correct
20	Correct	5 ms	6220 KB	Output is correct
21	Correct	3 ms	2892 KB	Output is correct
22	Correct	3 ms	4428 KB	Output is correct
23	Correct	5 ms	4044 KB	Output is correct
24	Correct	10 ms	12492 KB	Output is correct
25	Correct	82 ms	50504 KB	Output is correct