oj.uz

Submission #1042878

# Submission time Handle Problem Language Result Execution time Memory
1042878 2024-08-03T13:53:02 Z VMaksimoski008 Kas (COCI17_kas) C++17
70 / 100
 2000 ms 49648 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

bool dp[51][1005][1005];

signed main() {
    int n;
    cin >> n;

    ll sum = 0;
    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i], sum += v[i];

    dp[0][0][0] = 1;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=sum; j++) {
            for(int k=0; k<=sum-j; k++) {
                dp[i][j][k] = dp[i-1][j][k];
                if(v[i] <= j && dp[i-1][j-v[i]][k]) dp[i][j][k] = 1;
                if(v[i] <= k && dp[i-1][j][k-v[i]]) dp[i][j][k] = 1; 
            }
        }
    }

    ll ans = 0;
    for(int i=0; i<=sum; i++) if(dp[n][i][i]) ans = i + (sum - 2 * i);
    cout << ans << '\n';
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10220 KB Output is correct
2 Correct 12 ms 10292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10332 KB Output is correct
2 Correct 9 ms 10144 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10188 KB Output is correct
2 Correct 10 ms 11272 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12120 KB Output is correct
2 Correct 11 ms 13148 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13144 KB Output is correct
2 Correct 13 ms 13068 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 34900 KB Output is correct
2 Correct 36 ms 39764 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 44628 KB Output is correct
2 Correct 45 ms 49648 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 19220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 18512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 19428 KB Time limit exceeded
2 Halted 0 ms 0 KB -