oj.uz

Submission #493551

# Submission time Handle Problem Language Result Execution time Memory
493551 2021-12-12T02:48:20 Z blue Candies (JOI18_candies) C++17
0 / 100
 5000 ms 11620 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 = 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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 11620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5042 ms 11620 KB Time limit exceeded
2 Halted 0 ms 0 KB -