Submission #1304065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304065		exoworldgd	Kas (COCI17_kas)	C++20	0 / 100	101 ms	3572 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,M=1e9+7,inf=1e18;
int n,a[N+5],dp[2][N+5],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