oj.uz

Submission #493553

# Submission time Handle Problem Language Result Execution time Memory
493553 2021-12-12T02:52:19 Z blue Candies (JOI18_candies) C++17
0 / 100
 222 ms 332 KB 
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;

int main()
{
  int N;
  cin >> N;

  vll A(1+N);
  for(int i = 1; i <= N; i++) cin >> A[i];

  vll res(N - (N/2));
  for(int j = 1; j <= N - (N/2); j++)
  {
    ll lo = -2'000'000'000LL;
    ll hi = 2'000'000'000LL;
    while(1)
    {
      ll mid = (lo+hi + 10'000'000'000LL)/2 - 5'000'000'000LL;
      vector< pair<ll, int> > dp(1+N);
      dp[0] = {0, 0};
      dp[1] = max(pair<ll, int>{0, 0}, pair<ll, int>{A[1] - mid, -1});
      for(int i = 2; i <= N; i++)
      {
        dp[i] = max(dp[i-1], {dp[i-2].first + A[i] - mid, dp[i-2].second - 1});
      }

      if(lo == hi)
      {
        cout << dp[N].first - dp[N].second*mid << '\n';
        break;
      }
      else
      {
        if(-dp[N].second <= j)
          hi = mid;
        else
          lo = mid+1;
      }
    }
  }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 222 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -