Submission #493552

#	Time	Username	Problem	Language	Result	Execution time	Memory
493552		blue	Candies (JOI18_candies)	C++17	0 / 100	226 ms	580 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';
        break;
      }
      else
      {
        if(-dp[N].second <= j)
          hi = mid;
        else 
          lo = mid+1;
      }
    }
  }
}

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