제출 #1304063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304063		exoworldgd	Kas (COCI17_kas)	C++20	0 / 100	106 ms	4476 KiB

kas

#pragma GCC optimize("O5,unroll-loops,inline,fast-math")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+5,M=1e9+7,inf=1e18;
int n,a[N],dp[2][N],s=0;
signed main(void) {
	exoworldgd;
	cin >> n;
	for (int i=0; i<n; i++) cin >> a[i], s+=a[i];
	for (int i=0; i<N; i++) dp[0][i]=-inf; dp[0][N/2]=0;
	for (int i=1; i<=n; i++) for (int j=N; j+1; j--) dp[i&1][j]=max({dp[i&1^1][j],(j+a[i]<N?dp[i&1^1][j+a[i]]+a[i]:-inf),(j>=a[i]?dp[i&1^1][j-a[i]]:-inf)});
	cout << s-dp[n&1][N/2];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10