oj.uz

Submission #732243

# Submission time Handle Problem Language Result Execution time Memory
732243 2023-04-28T19:25:21 Z blackslex Kas (COCI17_kas) C++17
100 / 100
 156 ms 87248 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 505, M = 1e5 + 5;
int n, ans, a[N], dp[N][M];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ans += a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = M - 1; j >= 1; j--) if (dp[i - 1][j]) dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]), dp[i][abs(a[i] - j)] = max(dp[i][abs(a[i] - j)], dp[i - 1][j] + a[i]), dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        dp[i][a[i]] = max({dp[i][a[i]], dp[i - 1][0] + a[i], dp[i - 1][a[i]]}), dp[i][0] = max(dp[i][0], dp[i - 1][0]);
    }
    printf("%d", ans - (dp[n][0] >> 1));
}

Compilation message

kas.cpp: In function 'int main()':
kas.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
kas.cpp:10:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ans += a[i];
      |                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 8 ms 596 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16620 KB Output is correct
2 Correct 42 ms 5964 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 18556 KB Output is correct
2 Correct 105 ms 23216 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 40980 KB Output is correct
2 Correct 156 ms 87248 KB Output is correct