oj.uz

Submission #735665

# Submission time Handle Problem Language Result Execution time Memory
735665 2023-05-04T12:43:20 Z Nhoksocqt1 Kas (COCI17_kas) C++17
100 / 100
 237 ms 8168 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 5 ms 328 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 212 KB Output is correct
2 Correct 6 ms 212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8164 KB Output is correct
2 Correct 38 ms 8168 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8164 KB Output is correct
2 Correct 55 ms 8168 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1876 KB Output is correct
2 Correct 45 ms 1876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 1876 KB Output is correct
2 Correct 103 ms 1876 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 1876 KB Output is correct
2 Correct 237 ms 1880 KB Output is correct