Apple Division

input/code.cpp: In function 'long long int cal(long long int, long long int, long long int, const std::vector<long long int>&)':
input/code.cpp:36:13: warning: comparison of integer expressions of different signedness: 'const long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if (idx >= wt.size()) return sum;
      |         ~~~~^~~~~~~~~~~~

#include <bits/stdc++.h>

// int main() {
//     std::ios_base::sync_with_stdio(false);
//     std::cin.tie(nullptr);
//
//     long long n;
//     std::cin >> n;
//
//     long long sum = 0;
//     std::vector<long long> weights(n);
//     for (long long i = 0; i < n; i++) {
//         std::cin >> weights[i];
//         sum += weights[i];
//     }
//
//     const long long W = (sum + 1) / 2;
//
//     std::vector Matrix(W + 1,std::vector<long long>(n, 0));
//     for(int i = 1; i < n; i++){
//         for(int w = 1; w < W+1; w++){
//             if (weights[i - 1] > w) {
//                 Matrix[w][i] = Matrix[w][i-1];
//             } else {
//                 Matrix[w][i] = std::max(Matrix[w][i-1], Matrix[w-weights[i - 1]][i-1] + weights[i - 1]);
//             }
//         }
//     }
//
//     std::cout << std::abs(sum - 2 * Matrix[W][n - 1]) << std::endl;
//     return 0;
// }

long long cal(const long long idx, const long long W, const long long sum, const std::vector<long long> &wt) {
    if (sum > W) return 0;
    if (idx >= wt.size()) return sum;
    const long long a = cal(idx + 1, W, sum + wt[idx], wt);
    const long long b = cal(idx + 1, W, sum, wt);
    if (std::abs(W - a) < std::abs(W - b)) {
        return a;
    }
    return b;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long n;
    std::cin >> n;

    long long sum = 0;
    std::vector<long long> weights(n);
    for (long long i = 0; i < n; i++) {
        std::cin >> weights[i];
        sum += weights[i];
    }

    const long long W = (sum + 1) / 2;

    std::cout << std::abs(sum - 2 * cal(0, W, 0, weights)) << std::endl;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED