Cod sursa(job #1981469)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 15 mai 2017 19:52:22
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<bits/stdc++.h>
using namespace std;

long long s[100100];
int  v[101000];
struct pp {int a; int poz;};
pp bin[101000];
bool cmp (pp x, pp y) {
  if (x.a != y.a)
    return x.a < y.a;
  return x.poz < y.poz;
}
int main()
{
  int n, i, j, ok, nr, unde ,st, dr, mm1, mm2, m;
  scanf ("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf ("%d", &v[i]);
    s[i] = s[i - 1] + v[i];
    bin[i].a = v[i];
    bin[i].poz = i;
  }
  sort (bin + 1, bin + n + 1, cmp);
  ok = 0;
  for (i = 1; i <= n; i++) {
    if (s[i] * 2 == s[n])
      ok = 1;
    nr = s[i] * 2 - s[n];
    unde = 1;
    if (nr < 0) {
      unde = 2;
      nr = -nr;
    }
    st = 1;
    dr = n;
    mm1 = -1;
    while (st <= dr) {
      m = (st + dr) / 2;
      if (bin[m].a * 2>= nr) {
        dr = m - 1;
        if (bin[m].a * 2== nr)
          mm1 = m;
      }
      else
        st = m + 1;
    }
    st = 1;
    dr = n;
    mm2 = -1;
    while (st <= dr) {
      m = (st + dr) / 2;
      if (bin[m].a * 2<= nr) {
        st = m + 1;
        if (bin[m].a * 2== nr)
          mm2 = m;
      }
      else
        dr = m - 1;
    }
    if (mm1 != 1 && unde == 1 && bin[mm1].poz <= i)
      ok = 1;
    if (mm2 != 1 && unde == 2 && bin[mm2].poz > i)
      ok = 1;
  }
  if (ok == 0)
    printf ("NO");
  else
    printf ("YES");
  return 0;
}