oj.uz

Submission #1024018

# Submission time Handle Problem Language Result Execution time Memory
1024018 2024-07-15T10:39:36 Z kustizus Kas (COCI17_kas) C++17
100 / 100
 85 ms 1256 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen ("file.inp","r",stdin);
    // freopen ("file.out","w",stdout);
    int n, a, sum = 0;
    cin >> n;
    vector<int> dp(1e5 + 5, -1), bef(1e5 + 5, -1);
    bef[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        sum += a;
        for (int j = 0; j <= 1e5; j++)
            if (bef[j] != -1)
            {
                if (j + a <= 1e5)
                    dp[j + a] = max(dp[j + a], bef[j]);
                if (j >= a)
                    dp[j - a] = max(dp[j - a], bef[j] + a);
                else
                    dp[a - j] = max(dp[a - j], bef[j] + j);
            }
        for (int j = 0; j <= 1e5; j++)
        {
            bef[j] = max(dp[j], bef[j]);
            dp[j] = -1;
        }
    }
    cout << sum - bef[0];
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1224 KB Output is correct
2 Correct 2 ms 1116 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1112 KB Output is correct
2 Correct 9 ms 1116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1116 KB Output is correct
2 Correct 35 ms 1116 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1256 KB Output is correct
2 Correct 61 ms 1116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1116 KB Output is correct
2 Correct 85 ms 1112 KB Output is correct