fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7.  
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int n;
  12.     cin >> n;
  13.  
  14.     vector<ll> a(n);
  15.  
  16.     for (int i = 0; i < n; i++) {
  17.         cin >> a[i];
  18.     }
  19.  
  20.     // Sort initial rewards in decreasing order
  21.     sort(a.begin(), a.end(), greater<ll>());
  22.  
  23.     /*
  24.         prefix[i] =
  25.         maximum value of:
  26.  
  27.             a[j] + (j + 1)
  28.  
  29.         for j <= i
  30.  
  31.         This represents the maximum final score
  32.         among customers BEFORE the candidate.
  33.     */
  34.     vector<ll> prefix(n);
  35.  
  36.     for (int i = 0; i < n; i++) {
  37.  
  38.         ll value = a[i] + (i + 1);
  39.  
  40.         if (i == 0)
  41.             prefix[i] = value;
  42.         else
  43.             prefix[i] = max(prefix[i - 1], value);
  44.     }
  45.  
  46.     /*
  47.         suffix[i] =
  48.         maximum value of:
  49.  
  50.             a[j] + j
  51.  
  52.         for j >= i
  53.  
  54.         This represents the maximum final score
  55.         among customers AFTER the candidate.
  56.     */
  57.     vector<ll> suffix(n);
  58.  
  59.     for (int i = n - 1; i >= 0; i--) {
  60.  
  61.         ll value = a[i] + i;
  62.  
  63.         if (i == n - 1)
  64.             suffix[i] = value;
  65.         else
  66.             suffix[i] = max(suffix[i + 1], value);
  67.     }
  68.  
  69.     int answer = 0;
  70.  
  71.     // Try every customer as the winner
  72.     for (int i = 0; i < n; i++) {
  73.  
  74.         // Candidate wins and receives n tournament points
  75.         ll candidateScore = a[i] + n;
  76.  
  77.         ll bestOtherScore = LLONG_MIN;
  78.  
  79.         // Customers before i
  80.         if (i > 0) {
  81.             bestOtherScore = max(
  82.                 bestOtherScore,
  83.                 prefix[i - 1]
  84.             );
  85.         }
  86.  
  87.         // Customers after i
  88.         if (i + 1 < n) {
  89.             bestOtherScore = max(
  90.                 bestOtherScore,
  91.                 suffix[i + 1]
  92.             );
  93.         }
  94.  
  95.         // Candidate has the highest score
  96.         if (candidateScore >= bestOtherScore) {
  97.             answer++;
  98.         }
  99.     }
  100.  
  101.     cout << answer << '\n';
  102.  
  103.     return 0;
  104. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
3 
8 10 11
stdout
copy 
2
https://ideone.com/0Gk7sm
language:
C++ (gcc 8.3)
created:
9 hours 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!