oj.uz

Submission #238840

# Submission time Handle Problem Language Result Execution time Memory
238840 2020-06-13T07:47:30 Z Exile_2k4 Holding (COCI20_holding) C++17
0 / 110
 54 ms 102136 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

const int N = 101;

int a[N],dp[N][N][N*N/4], L[N][N*N/4] ,n,l,r,k,sum=0;

signed main(){
	cin >> n >> l >> r >> k;
	for(int i=1;i<=n;++i) cin >> a[i];
	sum = accumulate(a+l,a+r+1,sum);
	
	for(int i=l-1;i>0;--i){
		for(int j=l;j<=r;++j){
			for(int k=0;k<N*N/4;++k){
				dp[i][j][k] = max({dp[i][j][k],dp[i+1][j][k],dp[i][j-1][k]});
				int spend = j-i;
				if(k>=spend) dp[i][j][k] = max(dp[i][j][k],dp[i+1][j-1][k-spend]+a[j]-a[i]);
			}
		}
	}
	for(int i=l;i<=r;++i){
		for(int j=0;j<N*N/4;++j){
			L[i][j] = dp[1][i][j];
		}
	}
	memset(dp,0,sizeof(dp));
	for(int i=r;i>=l;--i){
		for(int j=r+1;j<=n;++j){
			for(int k=0;k<N*N/4;++k){
				dp[i][j][k] = max({dp[i][j][k],dp[i-1][j][k],dp[i][j+1][k]});
				int spend = j-i;
				if(k>=spend) dp[i][j][k] = max(dp[i][j][k], dp[i-1][j+1][k-spend]+a[i]-a[j]);
			}
		}
	}
	int ans = 1e9;
	for(int i=l;i<=r+1;++i){
		for(int j=0;j<N*N/4;++j){
			ans = min(ans,sum-L[i-1][j]-dp[i][n][k-j]);
		}
	}
	cout << ans;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 102136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 102136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 102136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 102136 KB Output isn't correct
2 Halted 0 ms 0 KB -