Gao The Sequence
Time Limit: 2 Seconds Memory Limit: 65536 KB
You are given a sequence of integers, A1,A2,...,An. And you are allowed a manipulation on the sequence to transform the origin sequence into another sequence B1,B2,...,Bn(Maybe the two sequences are same ). The manipulation is specified as the following three steps:
1.Select an integer Ai and choose an arbitrary positive integer delta as you like.
2.Select some integers Aj satisfying j < i, let's suppose the selected integers are Ak1,Ak2,...,Akt , then subtract an arbitrary positive integer Di from Aki (1 ≤ i ≤ t) as long as sum(Di) = delta.
3.Subtract delta from Ai.
The manipulation can be performed any times. Can you find a way to transform A1,A2,...,An to B1,B2,...,Bn ?
Input
The input consist of multiple cases. Cases are about 100 or so. For each case, the first line contains an integer N(1 ≤ N ≤ 10000) indicating the number of the sequence. Then followed by N lines, ith line contains two integers Ai and Bi (0 ≤ Bi ≤ Ai ≤ 4294967296).
Output
Output a single line per case. Print "YES" if there is a certain way to transform Sequence A into Sequence B. Print "NO" if not.
Sample Input
3
3 2
4 2
5 2
3
2 0
7 1
3 1
Sample Output
YES
NO
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL; LL a[];
int main()
{
LL n,i,x,y;
while(scanf("%lld",&n)>)
{
LL max1=-;
for(i=;i<=n;i++)
{
scanf("%lld%lld",&x,&y);
a[i]=x-y;
}
sort(a+,a++n);
max1=a[n];
LL sum=;
LL hxl=a[n];
for(i=;i<=n-;i++)
{
sum=sum+a[i];
hxl=(hxl+a[i])%;
}
if(max1>sum || hxl==) printf("NO\n");
else printf("YES\n");
}
return ;
}