Cerinta completa

Given an array, we define its value to be the value obtained by following these instructions:

  • Write down all pairs of numbers from this array.
  • Compute the product of each pair.
  • Find the sum of all the products.

For example, for a given array, for a given array [, , , ],

Pairs (7, 2), (7, -1), (7, 2), (2, -1), (2, 2), (-1, 2)
Products of the pairs 14, -7, 14, -2, 4, -2
Sum of the products 14 + (-7) + 14 + (-2) + 4 + (-2) =

Note that is listed twice, one for each occurrence of .

Given an array of integers, find the largest value of any of its nonempty subarrays.

Note: A subarray is a contiguous subsequence of the array.

Complete the function largestValue which takes an array and returns an integer denoting the largest value of any of the array’s nonempty subarrays.

Input Format

The first line contains a single integer , denoting the number of integers in array .
The second line contains space-separated integers denoting the elements of array .

Constraints

Subtasks

  • for 20% of the points.
  • for 70% of the points.

Output Format

Print a single line containing a single integer denoting the largest value of any of the array’s nonempty subarrays.

Sample Input 0

6
-3 7 -2 3 5 -2

Sample Output 0

41

Explanation 0

In this case, we have . The largest-valued subarray turns out to be with value .

Sample Input 1

10
5 7 -5 6 3 9 -8 2 -1 10

Sample Output 1

200

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))

int N;
ll A[505050];
ll ma;

template<typename V> struct ConvexHull {
    deque<pair<V,V>> Q;
    int cmptype=0; // 0-min 1-max
    V calc(pair<V,V> p, V x) {
        return p.first*x+p.second;
    }
    int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
        return cmptype^((B.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-B.first));
    }
    void add(V a, V b) { // add ax+b
        Q.push_back({a,b});
        int v;
        while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
            Q[v-2]=Q[v-1], Q.pop_back();
    }
    void add(vector<pair<V,V>> v) {
        sort(v.begin(),v.end());
        if(cmptype==1) reverse(v.begin(),v.end());
        for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second);
    }
    
    
    V query(V x) {
        int L=-1,R=Q.size()-1;
        while(R-L>1) {
            int M=(L+R)/2;
            (cmptype^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M;
        }
        return calc(Q[R],x);
    }
};

void dfs(int L,int R) {
    if(R-L<=1) return ;
    if(R-L==2) {
        ma=max(ma,A[L]*A[L+1]);
        return;
    }
    
    int M=L+(R-L)/2;
    dfs(L,M);
    dfs(M,R);
    vector<pair<ll,ll>> V;
    ll a=0,b=0;
    int i;
    
    for(i=M;i<R;i++) {
        b+=A[i]*a;
        a+=A[i];
        
        V.push_back({a,b});
    }
    sort(ALL(V));
    
    ConvexHull<ll> ch;
    FORR(v,V) {
        
        ch.add(v.first,v.second);
    }
    
    
    a=0,b=0;
    for(i=M-1;i>=L;i--) {
        b+=A[i]*a;
        a+=A[i];
        
        ma=max(ma,ch.query(a)+b);
    }
    
    
    
    
}

void solve() {
    int i,j,k,l,r,x,y; string s;
    
    cin>>N;
    FOR(i,N) cin>>A[i];
    
    dfs(0,N);
    
    cout<<ma<<endl;
    
}


int main(int argc,char** argv){
    string s;int i;
    if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
    FOR(i,argc-1) s+=argv[i+1],s+='n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
    cout.tie(0); solve(); return 0;
}

Scor obtinut: 1.0

Submission ID: 464653493

Link challenge: https://www.hackerrank.com/challenges/pair-sums/problem

Pair Sums