oj.uz

Submission #367984

# Submission time Handle Problem Language Result Execution time Memory
367984 2021-02-19T06:41:39 Z TosakaUCW Kas (COCI17_kas) C++17
100 / 100
 230 ms 198144 KB 
#include <stdio.h>
#include <algorithm>
#include <memory.h>

int read(int x = 0, int f = 0, char ch = getchar())
{
    while ('0' > ch or ch > '9')
        f = ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}

const int N = 5e2 + 5;
const int M = 1e5 + 5;

int n, sum, ans;
int a[N], f[N][M];

int main()
{
    n = read();
    for (int i = 1; i <= n; i++)
        sum += (a[i] = read());
    memset(f, 0xcf, sizeof f), f[0][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= sum; j++)
            f[i][j] = std::max(f[i - 1][j], f[i - 1][j + a[i]] + a[i]),
            f[i][j] = std::max(f[i][j], f[i - 1][abs(j - a[i])] + a[i]);
    return printf("%d", sum - f[n][0] / 2), 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 198068 KB Output is correct
2 Correct 106 ms 197996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 198144 KB Output is correct
2 Correct 102 ms 198044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 197996 KB Output is correct
2 Correct 101 ms 198124 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 198124 KB Output is correct
2 Correct 102 ms 197996 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 197996 KB Output is correct
2 Correct 101 ms 198016 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 198016 KB Output is correct
2 Correct 100 ms 197996 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 197996 KB Output is correct
2 Correct 101 ms 197996 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 197996 KB Output is correct
2 Correct 165 ms 198016 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 197996 KB Output is correct
2 Correct 222 ms 198124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 197996 KB Output is correct
2 Correct 230 ms 197996 KB Output is correct