Submission #735665

#	Time	Username	Problem	Language	Result	Execution time	Memory
735665		Nhoksocqt1	Kas (COCI17_kas)	C++17	100 / 100	237 ms	8168 KiB

kas

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef long long ll;

const int N = 505;
int a[N], f[2][1002][1002], dp[2][200002], n;

int solve(int idx, int sA, int sB, int sC) {
    if(idx > n) {
        return (sA == sB) ? sC : 1e9;
    }

    int res = min(solve(idx + 1, sA + a[idx], sB, sC), solve(idx + 1, sA, sB + a[idx], sC));
    return min(res, solve(idx + 1, sA, sB, sC + a[idx]));
}

int sub2() {
    for (int sA = 0; sA <= 1000; ++sA) {
        for (int sB = 0; sB <= 1000; ++sB) {
            f[0][sA][sB] = f[1][sA][sB] = 1e9;
        }
    }

    f[0][0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        int cur(i & 1), pre(!cur);
        for (int sA = 0; sA <= 1000; ++sA) {
            for (int sB = 0; sB <= 1000; ++sB) {
                if(f[pre][sA][sB] >= 1e9) {
                    continue;
                }

                f[cur][sA][sB] = min(f[cur][sA][sB], f[pre][sA][sB] + a[i]);
                if(sA + a[i] <= 1000)
                    f[cur][sA + a[i]][sB] = min(f[cur][sA + a[i]][sB], f[pre][sA][sB]);

                if(sB + a[i] <= 1000)
                    f[cur][sA][sB + a[i]] = min(f[cur][sA][sB + a[i]], f[pre][sA][sB]);

                f[pre][sA][sB] = 1e9;
            }
        }
    }

    int res(1e9);
    for (int s = 1000; s >= 0; --s) {
        if(f[n & 1][s][s] < 1e9) {
            res = s + f[n & 1][s][s];
            break;
        }
    }

    return res;
}

int full() {
    int off(100000);
    for (int s = 0; s <= 2 * off; ++s) {
        dp[0][s] = dp[1][s] = 1e9;
    }

    dp[0][off] = 0;
    for (int i = 1; i <= n; ++i) {
        int cur(i & 1), pre(!cur);
        for (int s = 0; s <= 2 * off; ++s) {
            if(dp[pre][s] >= 1e9)
                continue;

            dp[cur][s] = min(dp[cur][s], dp[pre][s] + a[i]);
            if(s - a[i] >= 0)
                dp[cur][s - a[i]] = min(dp[cur][s - a[i]], dp[pre][s]);

            if(s + a[i] <= 2 * off)
                dp[cur][s + a[i]] = min(dp[cur][s + a[i]], dp[pre][s]);

            dp[pre][s] = 1e9;
        }
    }

    int s(0);
    for (int i = 1; i <= n; ++i) {
        s += a[i];
    }

    return (s - dp[n & 1][off]) / 2 + dp[n & 1][off];
}

void process() {
    cin >> n;
    int s(0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }

    if(n <= 13) {
        int z = solve(1, 0, 0, 0);
        cout << (s - z) / 2 + z;
    } else
        if(s <= 1000) {
            cout << sub2();
        } else {
            cout << full();
        }
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	process();
	return 0;
}

Compilation message (stderr)

kas.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
kas.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

• 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