oj.uz

Submission #1109089

# Submission time Handle Problem Language Result Execution time Memory
1109089 2024-11-06T02:26:57 Z ind1v Kas (COCI17_kas) C++11
100 / 100
 196 ms 2120 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n;
int c[N];
int f[2][2 * A];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> c[i];
  }
  memset(f[0], 0x3f, sizeof(f[0]));
  f[0][A] = 0;
  for (int i = 1; i <= n; i++) {
    memset(f[i & 1], 0x3f, sizeof(f[i & 1]));
    for (int j = 0; j < 2 * A; j++) {
      f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j] + c[i]);
      if (j >= c[i]) {
        f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j - c[i]]);
      }
      if (j + c[i] < 2 * A) {
        f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j + c[i]]);
      }
    }
  }
  long long sum = accumulate(c + 1, c + n + 1, 0LL);
  cout << (sum - f[n & 1][A]) / 2 + f[n & 1][A] << '\n';
  return 0;
}

Compilation message

kas.cpp: In function 'int main()':
kas.cpp:24:42: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   24 |       f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j] + c[i]);
      |                                        ~~^~~
kas.cpp:26:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |         f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j - c[i]]);
      |                                          ~~^~~
kas.cpp:29:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   29 |         f[i & 1][j] = min(f[i & 1][j], f[i & 1 ^ 1][j + c[i]]);
      |                                          ~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2028 KB Output is correct
2 Correct 6 ms 1872 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1872 KB Output is correct
2 Correct 17 ms 1872 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2024 KB Output is correct
2 Correct 20 ms 1872 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1872 KB Output is correct
2 Correct 92 ms 1872 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 1872 KB Output is correct
2 Correct 148 ms 2040 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 2120 KB Output is correct
2 Correct 193 ms 1872 KB Output is correct