Contest Div1 : Here
Contest Div2 : Here
Contest Div3 : Here
Setter : Pratik Kumar
Tester : Aryan Choudhary
DIFFICULTY
Easy
Pre Requisites
None
Explanation :
The idea for the solution is that, if you have a sequence S_1 = 1 < S_2 < \dots < S_{k-1} < S_k = N, such that you jump from stone S_i to S_{i+1} for all i \in [1, k-1], the cost of this sequence c(S) = \sum_{i=1}^{k-1} (S_{i+1} - S_i + 1) \times A_{S_i} - A_{S_{i+1}}. Note that if, for any i \in [1, k-2], A_{S_i} \leq A_{S_{i+1}}, then the sequence S' = \{S_1, S_2, \dots, S_i, S_{i+2}, \dots, S_N\} has c(S') \geq c(S). Therefore, the shortest sequence S with c(S) minimised has A_{S_{i}} > A_{S_{i+1}} for all i \in [1, k-2]. Now, note that if there exists x such that S_i < x < S_{i+1} with A_{S_i} > A_x, then the sequence S' = \{S_1, S_2, \dots, S_i, x, S_{i+1}, \dots, S_k\} has c(S) > c(S').
Therefore, we can calculate the optimal sequence S by starting with S_1 = 1 and then, if you have already found S_1, S_2, \dots, S_y, set S_{y+1} as the least z > y such that A_z < A_y, or N if no such z exists.
Once you have found this sequence S, we can calculate c(S) in O(N), and output max(0, c(S)).
Time Complexity
O(N)
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void solve()
{
int n;
cin >> n;
int arr[n];
for(int i = 0; i<n; i++)cin >> arr[i];
ll ans = arr[0];
int mn = arr[0];
for(int i = 1; i<n; i++)
{
ans += mn;
mn = min(mn,arr[i]);
}
ans -= arr[n-1];
ans = max(0LL,ans);
cout << ans << "\n";
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int t = 1;
cin>> t;
for(int i = 1; i<=t; i++) {
solve();
}
return 0;
}
Tester
/*
Compete against Yourself.
Author - Aryan (@aryanc403)
*/
/*
Credits -
Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
*/
#ifdef ARYANC403
#include <header.h>
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define dbg(args...) 42;
#define endl "\n"
#endif
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
Fun fun_;
public:
template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define repA(i,j,n) for(i=(j);i<=(n);++i)
#define repD(i,j,n) for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
template <class T>
using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
vi readVectorInt(int n,lli l,lli r){
vi a(n);
for(int i=0;i<n-1;++i)
a[i]=readIntSp(l,r);
a[n-1]=readIntLn(l,r);
return a;
}
// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
// vector<vi> e(n);
// atcoder::dsu d(n);
// for(lli i=1;i<n;++i){
// const lli u=readIntSp(1,n)-1;
// const lli v=readIntLn(1,n)-1;
// e[u].pb(v);
// e[v].pb(u);
// d.merge(u,v);
// }
// assert(d.size(0)==n);
// return e;
// }
const lli INF = 0xFFFFFFFFFFFFFFFLL;
const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{ return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end()) m.insert({x,cnt});
else jt->Y+=cnt;
}
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt) m.erase(jt);
else jt->Y-=cnt;
}
bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
const lli mod = 1000000007L;
// const lli maxN = 1000000007L;
//Original Code: https://www.codechef.com/viewsolution/8424830
struct cht{
struct Line{
lli a;
lli b;
lli val;
double xLeft;
bool type;
Line(lli _a = 0 , lli _b = 0){
a = _a;
b = _b;
xLeft = -INF;
type = 0;
val = 0;
}
lli valueAt(lli x) const{
return 1LL * a * x + b;
}
friend bool areParallel(const Line &l1, const Line &l2){
return l1.a == l2.a;
}
friend double intersectX(const Line &l1 , const Line &l2){
return areParallel(l1 , l2) ? INF : (l2.b - l1.b) / (double) (l1.a - l2.a);
}
bool operator < (const Line &l2) const{
if(!l2.type)
return a < l2.a;
return xLeft > l2.val;
}
};
set < Line > hull;
void init(){
hull.clear();
}
bool hasPrev(set < Line > :: iterator it){
return it != hull.begin();
}
bool hasNext(set < Line > :: iterator it){
return it != hull.end() && next(it) != hull.end();
}
bool irrelevant(const Line &l1 , const Line &l2 , const Line &l3){
return intersectX(l1,l3) <= intersectX(l1,l2);
}
bool irrelevant(set < Line > :: iterator it){
return hasPrev(it) && hasNext(it) && (irrelevant(*next(it) , *it , *prev(it)));
}
set < Line > :: iterator updateLeftBorder(set < Line > :: iterator it){
if(!hasNext(it)){
return it;
}
double val = intersectX(*it , *next(it));
Line buf(*it);
it = hull.erase(it);
buf.xLeft = val;
it = hull.insert(it, buf);
return it;
}
void addLine(lli a , lli b){
// dbg("add",a,b);
Line l3 = Line(a, b);
auto it = hull.lower_bound(l3);
if(it != hull.end() && areParallel(*it , l3)){
if(it -> b > b){
it = hull.erase(it);
}
else{
return;
}
}
it = hull.insert(it, l3);
if(irrelevant(it)){
hull.erase(it);
return;
}
while(hasPrev(it) && irrelevant(prev(it))){
hull.erase(prev(it));
}
while(hasNext(it) && irrelevant(next(it))){
hull.erase(next(it));
}
it = updateLeftBorder(it);
if(hasPrev(it)){
updateLeftBorder(prev(it));
}
if(hasNext(it)){
updateLeftBorder(next(it));
}
}
lli getBest(lli x){
// assert(!hull.empty());
if(hull.empty())
return INF;
Line q;
q.val = x;
q.type = 1;
auto bestLine = hull.lower_bound(q);
if(bestLine == hull.end()){
return INF;
}
return bestLine -> valueAt(x);
}
};
lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
vi a;
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,2500);
lli sumN = 5e5,maxN=1e5;
while(T--)
{
const int n=readIntLn(1,min(sumN,maxN));
sumN-=n;
auto a=readVectorInt(n,1,1e9);
vi dp(n,INF);
dp[0]=0;
cht c;
c.addLine(a[0],a[0]);
for(int j=1;j<n;++j){
dp[j]=-a[j]+c.getBest(j);
const int i=j;
c.addLine(a[i],dp[i]+(-i+1)*a[i]);
}
cout<<max(0LL,dp[n-1])<<endl;
} aryanc403();
readEOF();
return 0;
}