Submission #1017157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017157		rxlfd314	Feast (NOI19_feast)	C++17	100 / 100	604 ms	23380 KiB

feast

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
using arl4 = array<ll, 4>;
 
#define vt vector
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
void solve();

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int T = 1;
  //cin >> T;
  FOR(t, 1, T) {
    solve();
  }
}

void solve() {
  int N, K;
  cin >> N >> K;
  vt<int> A(N+1);
  FOR(i, 1, N)
    cin >> A[i];
  
  vt<array<pair<ld, int>, 2>> dp(N+1);
  auto calc = [&](ld pen) {
    dp[0][1] = {-3e14, 0};
    dp[0][0] = {0, 0};
    FOR(i, 1, N) {
      dp[i][1] = make_pair(dp[i-1][1].first + A[i], dp[i-1][1].second);
      dp[i][1] = max(dp[i][1], make_pair(dp[i-1][0].first + A[i] - pen, dp[i-1][0].second - 1));
      dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
    }
  };
  
  ld lo = 0, hi = 3e14;
  FOR(_, 1, 100) {
    ld mid = (lo + hi) / 2.0;
    calc(mid);
    if (-max({dp[N][0], dp[N][1]}).second <= K)
      hi = mid;
    else
      lo = mid;
  }
  
  calc(lo);  
  cout << (ll)round(max(dp[N][0], dp[N][1]).first + lo * K) << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29