Submission #1307517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307517		Zone_zonee	Kas (COCI17_kas)	C++20	100 / 100	113 ms	2008 KiB

kas

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10, M = 1e5+10;

int dp[2][2*M], a[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
    memset(dp, 0xff, sizeof dp);
    dp[0][sum] = 0;
    for(int i = 0; i < n; ++i){
        int cur = i&1, nxt = cur^1;
        for(int j = 0; j <= 2*sum; ++j){
            if(dp[cur][j] == -1) continue;
            if(j+a[i+1] <= 2*sum+1) dp[nxt][j+a[i+1]] = max(dp[nxt][j+a[i+1]], dp[cur][j]+a[i+1]);
            if(j >= a[i+1]) dp[nxt][j-a[i+1]] = max(dp[nxt][j-a[i+1]], dp[cur][j]);
            dp[nxt][j] = max(dp[nxt][j], dp[cur][j]);
        }
    }
    cout << sum - dp[n&1][sum] << '\n';
}

• 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