fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. bool is_possible(int n, const vector<ll>& a, ll k) {
  7.     // dp[used][i] where used is 0 or 1, and i is the index
  8.     // Initialize two vectors for used=0 and used=1
  9.     // dp0[i] means used=0 at position i
  10.     // dp1[i] means used=1 at position i
  11.     vector<bool> dp0(n + 1, false);
  12.     vector<bool> dp1(n + 1, false);
  13.     dp0[0] = true;
  14.     dp1[0] = false;
  15.  
  16.     for(int i = 0; i < n; ++i){
  17.         // Temporary next step
  18.         // Iterate through current dp0 and dp1
  19.         // Handle dp0
  20.         if(dp0[i]){
  21.             // Option 1: pair a[i] with a[i+1] if possible
  22.             if(i+1 <n && a[i+1] - a[i] <=k){
  23.                 dp0[i+2] = true;
  24.             }
  25.             // Option 2: pair a[i] with an extra cell, if not used yet
  26.             if(k >=1){
  27.                 dp1[i+1] = true;
  28.             }
  29.         }
  30.         // Handle dp1
  31.         if(dp1[i]){
  32.             // Option 1: pair a[i] with a[i+1] if possible
  33.             if(i+1 <n && a[i+1] - a[i] <=k){
  34.                 dp1[i+2] = true;
  35.             }
  36.             // No option to pair with extra cell since already used
  37.         }
  38.         // Update dp0 and dp1
  39.     }
  40.     return dp0[n] || dp1[n];
  41. }
  42.  
  43. int main(){
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(0);
  46.     int t;
  47.     cin >> t;
  48.     while(t--){
  49.         int n;
  50.         cin >> n;
  51.         vector<ll> a(n);
  52.         for(auto &x: a) cin >> x;
  53.         // Binary search for minimal k
  54.         ll left = 0, right = (ll)1e18;
  55.         ll answer = right;
  56.         while(left <= right){
  57.             ll mid = left + (right - left)/2;
  58.             if(is_possible(n, a, mid)){
  59.                 answer = mid;
  60.                 right = mid -1;
  61.             }
  62.             else{
  63.                 left = mid +1;
  64.             }
  65.         }
  66.         cout << left << "\n";
  67.     }
  68. }
  69.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13
stdout
copy 
1
1
2
3
https://ideone.com/c9UWug
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!