UVA11401

Someone helps me solve this problem please, I can't come up with any ideas to solve.

Thanks in advance.

UVa 1315

Someone help me solve this problem please, I don't know how to find formula for this problem

Given two arrays a and b, both arrays have size n. Find m the length of longest subsequence of i (1 <= i1 <= i2 <= i3 <= im) such that max(a[i1],a[i2],...,a[im]) + sum(b[i1],b[i2],...,b[im]) <= S , with S is given.

Constraints : n <= 10^5 , 1 <= a[i],b[i] <= 10^9

S <= 10^18

a[i] < a[i+1] for every 1 <= i <= n-1 (array a is increasing)

Input : First line : n,S

The following n lines : a[i] b[i]

An example test: Input:

4 10

1 5

2 1

3 3

4 2

Output :

3

Explain: Chosen subsequence is (2,3,4) (1-indexed).

Given an array a consisting of n elements, call array b consisting of n elements such that (a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2 is minimum and sum of all elements of array B is equal to m.

Given n, array A, m, find the value of (a[1] — b[1])^2 + (a[2] — b[2])^2 + ... + (a[n] — b[n])^2.

Constraints : 1 <= n <= 1e5 , 1 <= m <= 2e9, 1 <= a[i] <= 2e9

Input : first line n,m respectively, second line is the elements of array A Output : the expected value

Ex:

Input : 3 3
        3 4 5
Output : 27
Input : 10 4
        2 3 4 5
Output : 4