fork download 
  1. //Nicky.Rio
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define N 1000100
  7.  
  8. int n, a[N], cntMax[N], cntMin[N];
  9. long long MAX[N], MIN[N];
  10.  
  11. int main() {
  12.     //freopen("E:\\input.txt","r",stdin);
  13.     //double ss = clock();
  14.     cin.tie(NULL);cout.tie(NULL);
  15.     scanf("%d", &n);
  16.     for (int i = 0; i<n; i++) scanf("%d", &a[i]);
  17.     long long sum = 0;
  18.     MIN[n] = 1e16;
  19.     MAX[n] = -1e16;
  20.     for (int i = n - 1; i>=0; i--) {
  21.         sum += 1ll * a[i];
  22.         //
  23.         if (sum < MIN[i + 1]) {
  24.             MIN[i] = sum;
  25.             cntMin[i] = 1;
  26.         }
  27.         else {
  28.             if (sum == MIN[i + 1]) {
  29.                 MIN[i] = MIN[i + 1];
  30.                 cntMin[i] = cntMin[i + 1] + 1;
  31.             }
  32.             else {
  33.                 MIN[i] = MIN[i + 1];
  34.                 cntMin[i] = cntMin[i + 1];
  35.             }
  36.         }
  37.         //
  38.         if (sum > MAX[i + 1]) {
  39.             MAX[i] = sum;
  40.             cntMax[i] = 1;
  41.         }
  42.         else {
  43.             if (sum == MAX[i + 1]) {
  44.                 MAX[i] = MAX[i + 1];
  45.                 cntMax[i] = cntMax[i + 1] + 1;
  46.             }
  47.             else {
  48.                 MAX[i] = MAX[i + 1];
  49.                 cntMax[i] = cntMax[i + 1];
  50.             }
  51.         }
  52.     }
  53.     long long ans = -1e16;
  54.     long long cnt = 0;
  55.     sum = 0;
  56.     for (int i = 0; i<n - 1; i++) {
  57.         sum += a[i];
  58.         if (sum >= MIN[i + 1]) {
  59.             long long tmp = sum - MIN[i + 1];
  60.             if (tmp == ans) cnt += cntMin[i + 1];
  61.             else {
  62.                 if (tmp > ans) {
  63.                     cnt = cntMin[i + 1];
  64.                     ans = tmp;
  65.                 }
  66.             }
  67.         }
  68.         if (sum <=MAX[i + 1]) {
  69.             if (sum == MAX[i + 1] && MAX[i + 1] == MIN[i + 1]) continue;
  70.             long long tmp = MAX[i + 1] - sum;
  71.             if (tmp == ans) cnt += cntMax[i + 1];
  72.             else {
  73.                 if (tmp > ans) {
  74.                     cnt = cntMax[i + 1];
  75.                     ans = tmp;
  76.                 }
  77.             }
  78.         }
  79.     }
  80.     printf("%lld %lld", ans, cnt);
  81.     //double tt = clock();
  82.     //int ttt = (tt - ss) / CLOCKS_PER_SEC * 1000;
  83.     //printf("\nTime : %d", ttt);
  84. }
  85.  
Success #stdin #stdout 0s 42584KB
comments ()
stdin 
Standard input is empty
stdout 
-10000000000000000 0
https://ideone.com/BNYqU2
problem QTSEQ, based on SPOJ submission 19849529 (CPP14), 2017-07-23 17:37:16
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!