Cerinta completa

Consider an array, , of integers. We define the following terms:

  • Subsequence
    A subsequence of is an array that’s derived by removing zero or more elements from without changing the order of the remaining elements. Note that a subsequence may have zero elements, and this is called the empty subsequence.

  • Strictly Increasing Subsequence
    A non-empty subsequence is strictly increasing if every element of the subsequence is larger than the previous element.

  • Subarray
    A subarray of is an array consisting of a contiguous block of ‘s elements in the inclusive range from index to index . Any subarray of can be denoted by .

The diagram below shows all possible subsequences and subarrays of :

image

We define the following functions:

  • = the maximum sum of some strictly increasing subsequence in subarray

We define the goodness, , of array to be:

In other words, is the maximum possible value of for all possible subarrays of array .

Let be the length of the smallest subarray such that . Given , find the value of as well as the number of subarrays such that and , then print these respective answers as space-separated integers on a single line.

Input Format

The first line contains an integer, , denoting number of elements in array .
The second line contains space-separated integers describing the respective values of .

Constraints

Subtasks

For the of the maximum score:

For the of the maximum score:

Output Format

Print two space-seperated integers describing the respective values of and the number of subarrays satisfying and .

Sample Input 0

3
2 3 1

Sample Output 0

1 1

Explanation 0

The figure below shows how to calculate :

image

is the length of the smallest subarray satisfying . From the table, we can see that . There is only one subarray of length such that .

Limbajul de programare folosit: cpp14

Cod:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <assert.h>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pdd pair<double,double>
#define pii pair<ll,ll>
#define PI 3.14159265358979323846
#define MOD 1000000007
#define MOD2 1000000009
#define INF ((ll)1e+18)
#define x1 fldgjdflgjhrthrl
#define x2 fldgjdflgrtyrtyjl
#define y1 fldggfhfghjdflgjl
#define y2 ffgfldgjdflgjl
#define N 262134
#define SUM 23423
#define MAG 100000000
#define OPEN 0
#define CLOSE 1
typedef int ll;
typedef long double ld;
using namespace std;
ll i,j,n,k,l,m,tot, flag,r,ans,z, K,x1,y1,x2,y2,x3,y3,x,y,h,num,h2,timer,sz,q,c;
ll dp[41][821], a[200500], b[41][825], pa[200500];
pii t[500500];
void build() {  // build the tree
  for (int i = N - 1; i > 0; --i) t[i] = min(t[i<<1], t[i<<1|1]);
}

pii query(int l, int r) {  // sum on interval [l, r)
  pii res = mp(MOD,0);
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res, t[l++]);
    if (r&1) res = min(res, t[--r]);
  }
  return res;
}


int main() {
    //freopen("input.txt","r",stdin);
     //freopen("output.txt","w",stdout);
     h = 820;
    for (i = 0; i <= 40; i++)
        for (j = 0; j <= h; j++)
            dp[i][j] = b[i][j] = -1;
     cin >> n;
     assert(n >= 1 && n <= 200000);
     for (i = 0; i < n; i++)
     {
        cin >> a[i];
        assert(-40 <= a[i] && a[i] <= 40);
        pa[i+1] = pa[i] + a[i];
        t[N+i+1] = mp(pa[i+1], -i-1);
    }
    build();
    ll ans = 0, len = 0, cnt = 0;
    for (i = 0; i < n; i++)
    if (a[i] > 0)
    {
        dp[a[i]][a[i]] = i;
        b[a[i]][a[i]] = i;
        ll val = a[i]*(a[i]-1)/2;
        ll to = a[i];
        //for (j = 1; j < to; j++)
            for (k = 1; k <= val; k++)
            {
                dp[to][k+to] = max(dp[to][k+to], b[to-1][k]);
                b[to][k+to] = max(b[to][k+to], dp[to][k+to]);
            }
        for (j = to+1; j <= 40; j++)
            for (k = to; k <= val+to; k++)
                b[j][k] = max(b[j][k], b[j-1][k]);
        ll cur = -1, lst = -1, cur_sum = -1;
        for (j = h; j >= a[i]; j--)
        {
            if (b[40][j] > cur)
            {
               lst = cur, cur = b[40][j], cur_sum = j;
                pii mn = query(lst+1, cur+1);
                mn.Y = -mn.Y;
                ll val1 = pa[i+1]-mn.X-cur_sum, val2 = i-mn.Y;
                if (ans < val1)
                {
                   ans = val1, cnt = 1, len = val2;
                }
                else
                if (ans == val1)
                {
                   if (val2 < len)
                      cnt = 1, len = val2;
                   else
                   if (val2 == len)
                          cnt++;
                }
            }
        }
    }
    if (ans == 0)
       cnt = n;
    cout << ans << " " << cnt << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464647465

Link challenge: https://www.hackerrank.com/challenges/two-subarrays/problem

Two Subarrays