제출 #493551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493551		blue	Candies (JOI18_candies)	C++17	0 / 100	5042 ms	11620 KiB

candies

#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 = 0;
    ll hi = 2'000'000'000LL;
    while(1)
    {
      ll mid = (lo+hi)/2;
      vector< pair<ll, int> > dp(1+N);
      dp[0] = pair<ll, int>{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], pair<ll, int>{dp[i-2].first + A[i] - mid, dp[i-2].second - 1});
      }
      
      if(lo == hi)
      {
        cout << dp[N].first + dp[N].second*mid << '\n';
      }
      else
      {
        if(-dp[N].second <= mid)
          hi = mid;
        else 
          lo = mid+1;
      }
    }
  }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92