Cerinta completa
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence.
You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),…, (aN, wN)].
For a subseqence B = [(b1, v1), (b2, v2), …., (bM, vM)] of the given sequence :
- We call it increasing if for every i (1 <= i < M ) , bi < bi+1.
- Weight(B) = v1 + v2 + … + vM.
Task:
Given a sequence, output the maximum weight formed by an increasing subsequence.
Input:
The first line of input contains a single integer T. T test-cases follow. The first line of each test-case contains an integer N. The next line contains a1, a2 ,… , aN separated by a single space. The next line contains w1, w2, …, wN separated by a single space.
Output:
For each test-case output a single integer: The maximum weight of increasing subsequences of the given sequence.
Constraints:
1 <= T <= 5
1 <= N <= 150000
1 <= ai <= 109, where i ∈ [1..N]
1 <= wi <= 109, where i ∈ [1..N]
Sample Input:
2
4
1 2 3 4
10 20 30 40
8
1 2 3 4 1 2 3 4
10 20 30 40 15 15 15 50
Sample Output:
100
110
Explanation:
In the first sequence, the maximum size increasing subsequence is 4, and there’s only one of them. We choose B = [(1, 10), (2, 20), (3, 30), (4, 40)], and we have Weight(B) = 100.
In the second sequence, the maximum size increasing subsequence is still 4, but there are now 5 possible subsequences:
1 2 3 4
10 20 30 40
1 2 3 4
10 20 30 50
1 2 3 4
10 20 15 50
1 2 3 4
10 15 15 50
1 2 3 4
15 15 15 50
Of those, the one with the greatest weight is B = [(1, 10), (2, 20), (3, 30), (4, 50)], with Weight(B) = 110.
Please note that this is not the maximum weight generated from picking the highest value element of each index. That value, 115, comes from [(1, 15), (2, 20), (3, 30), (4, 50)], which is not a valid subsequence because it cannot be created by only deleting elements in the original sequence.
Limbajul de programare folosit: cpp14
Cod:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
using namespace std;
#define GI ({int new_input;scanf("%d",&new_input);new_input;})
typedef unsigned long long ll;
ll Tree[800000];
void updateTree(int b, int e, int p, ll val, int idx=1) {
if(p < b || p > e) return ;
if(p == b && p == e){
Tree[idx] = max(Tree[idx],val);
return ;
}
int mid = (b+e)/2;
int lt = (idx<<1);
int rt = ((idx<<1)+1);
updateTree(b, mid, p, val, lt);
updateTree(mid+1, e, p, val, rt);
Tree[idx] = max(Tree[lt], Tree[rt]);
return ;
}
ll query(int b,int e,int start,int end,int node){
if(e<start || b>end)return 0;
if(b<=start && e>=end)return Tree[node];
int mid=(start+end)>>1;
return max(query(b,e,start,mid,node*2),query(b,e,mid+1,end,node*2+1));
}
ll input[200000];
ll w[200000];
map<ll,int>m;
set<ll>s;
int main() {
int t=GI;
while(t--){
m.clear();s.clear();
s.empty();
memset(Tree,0,sizeof Tree);
int n=GI;
for(int i=0;i<n;i++){
scanf("%lld",&input[i]);
s.insert(input[i]);
}
for(int i=0;i<n;i++){
scanf("%lld",&w[i]);
}
int in=1;
set<ll>::iterator it;
for(it=s.begin();it!=s.end();it++){
m[*it]=in;
in++;
}in--;
ll ans=0;
for(int i=0;i<n;i++){
int mapped=m[input[i]];
if(mapped==1){
updateTree(1,in,mapped,w[i],1);
ans=max(ans,w[i]);
}
else{
ll get=query(1,mapped-1,1,in,1);
ans=max(ans,get+w[i]);
updateTree(1,in,mapped,w[i]+get,1);
}
}
cout<<ans<<endl;
}
return 0;
}
Scor obtinut: 1.0
Submission ID: 464653383
Link challenge: https://www.hackerrank.com/challenges/subsequence-weighting/problem