답안 #642043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642043	2022-09-18T10:38:09 Z	valerikk	Candies (JOI18_candies)	C++17	8 / 100	5000 ms	26004 KB

candies

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = 2e18;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  vector<ll> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  vector dp(n + 1, vector<ll>(2, -INF));
  dp[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    vector ndp(n + 1, vector<ll>(2, -INF));
    for (int j = 0; j <= n; ++j) {
      for (int f = 0; f < 2; ++f) {
        if (dp[j][f] == -INF) continue;
        for (int t = 0; t < 2 - f; ++t) {
          ndp[j + t][t] = max(ndp[j + t][t], dp[j][f] + a[i] * t);
        }
      }
    }
    dp = ndp;
  }

  vector<ll> ans((n + 1) / 2 + 1, -INF);
  for (int i = 0; i <= n; ++i) {
    if (dp[i][0] != -INF) {
      ans[i] = max(ans[i], dp[i][0]);
    }
    if (dp[i][1] != -INF) {
      ans[i] = max(ans[i], dp[i][1]);
    }
  }

  for (int i = 1; i < (n + 1) / 2; ++i) {
    assert(ans[i] - ans[i - 1] >= ans[i + 1] - ans[i]);
  }
  for (int i = 1; i <= (n + 1) / 2; ++i) {
    cout << ans[i] << "\n";
  }
  return 0;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	588 KB	Output is correct
2	Correct	175 ms	552 KB	Output is correct
3	Correct	179 ms	560 KB	Output is correct
4	Correct	198 ms	560 KB	Output is correct
5	Correct	185 ms	556 KB	Output is correct
6	Correct	183 ms	556 KB	Output is correct
7	Correct	209 ms	556 KB	Output is correct
8	Correct	187 ms	564 KB	Output is correct
9	Correct	184 ms	556 KB	Output is correct
10	Correct	180 ms	568 KB	Output is correct
11	Correct	194 ms	468 KB	Output is correct
12	Correct	171 ms	564 KB	Output is correct
13	Correct	172 ms	576 KB	Output is correct
14	Correct	172 ms	568 KB	Output is correct
15	Correct	195 ms	468 KB	Output is correct
16	Correct	180 ms	552 KB	Output is correct
17	Correct	179 ms	572 KB	Output is correct
18	Correct	176 ms	468 KB	Output is correct
19	Correct	188 ms	572 KB	Output is correct
20	Correct	174 ms	556 KB	Output is correct

Subtask #2

0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	588 KB	Output is correct
2	Correct	175 ms	552 KB	Output is correct
3	Correct	179 ms	560 KB	Output is correct
4	Correct	198 ms	560 KB	Output is correct
5	Correct	185 ms	556 KB	Output is correct
6	Correct	183 ms	556 KB	Output is correct
7	Correct	209 ms	556 KB	Output is correct
8	Correct	187 ms	564 KB	Output is correct
9	Correct	184 ms	556 KB	Output is correct
10	Correct	180 ms	568 KB	Output is correct
11	Correct	194 ms	468 KB	Output is correct
12	Correct	171 ms	564 KB	Output is correct
13	Correct	172 ms	576 KB	Output is correct
14	Correct	172 ms	568 KB	Output is correct
15	Correct	195 ms	468 KB	Output is correct
16	Correct	180 ms	552 KB	Output is correct
17	Correct	179 ms	572 KB	Output is correct
18	Correct	176 ms	468 KB	Output is correct
19	Correct	188 ms	572 KB	Output is correct
20	Correct	174 ms	556 KB	Output is correct
21	Execution timed out	5062 ms	26004 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-