Submission #1304067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304067		exoworldgd	Kas (COCI17_kas)	C++20	100 / 100	108 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-1]<=N?dp[(i&1)^1][j+a[i-1]]+a[i-1]:-inf),(j>=a[i-1]?dp[(i&1)^1][j-a[i-1]]:-inf)});
    cout << s-dp[n&1][N/2];
}

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