fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define sz(s) (int)s.size()
  6. #define FOR(i,a,b) for(int i=a;i<=b;++i)
  7. #define REP(i,a,b) for(int i=a;i>=b;--i)
  8.  
  9. using namespace std;
  10.  
  11. using ll = long long;
  12. using pii = pair<int, int>;
  13.  
  14. const int N = 3e5 + 5;
  15. const int mod = 1e9 + 7;
  16. const int base = 31;
  17. const ll INF = 1e18;
  18.  
  19. /// CODE ///
  20. int n;
  21. ll a[N], pre[N];
  22.  
  23.  
  24. namespace Sub1{
  25.     bool checkSub1(){
  26.         return n <= 1000;
  27.     }
  28.  
  29.     void solveSub1(){
  30.         int cnt = 0;
  31.  
  32.         FOR(i, 1, n){
  33.             ll mx = -1;
  34.             ll sum = 0;
  35.             FOR(j, i, n){
  36.                 mx = max(mx, a[j]);
  37.                 sum += a[j];
  38.                 if (2 * mx > sum) cnt++;
  39.             }
  40.         }
  41.         cout << cnt;
  42.     }
  43. }
  44.  
  45. namespace Sub2{
  46.     bool checkSub2(){
  47.         FOR(i, 1, n) if (a[i] < a[i-1]) return 0;
  48.         return 1;
  49.     }
  50.  
  51.     void solveSub2(){
  52.         ll cnt = 0;
  53.         FOR(i, 1, n){
  54.             int l = 1, r = i, ans = -1;
  55.             while (l <= r){
  56.                 int mid = (l + r) / 2;
  57.                 if (2 * a[i] > pre[i] - pre[mid - 1]){
  58.                     ans = mid;
  59.                     r = mid - 1;
  60.                 } else l = mid + 1;
  61.             }
  62.  
  63.             cnt += (i - l + 1);
  64.         }
  65.  
  66.         cout << cnt;
  67.     }
  68. }
  69.  
  70. void input(){
  71.     cin >> n;
  72.     FOR(i, 1, n) cin >> a[i];
  73.     FOR(i, 1, n) pre[i] = pre[i-1] + a[i];
  74. }
  75.  
  76. signed main(){
  77.     #define NAME "max"
  78.     if (fopen(NAME".inp", "r")){
  79.         freopen(NAME".inp", "r", stdin);
  80.         freopen(NAME".out", "w", stdout);
  81.     }
  82.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  83.  
  84.     input();
  85.     if (Sub1::checkSub1()) return Sub1::solveSub1(), 0;
  86.     if (Sub2::checkSub2()) return Sub2::solveSub2(), 0;
  87.  
  88.  
  89.     return 0;
  90. }
  91.  
  92.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NKVvrG
language:
C++14 (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!