Convex hull trick/commando.cpp - Revision history

101.60.169.14 at 14:31, 11 March 2016

2016-03-11T14:31:46Z

101.60.169.14 at 14:29, 11 March 2016

2016-03-11T14:29:44Z

180.211.180.26 at 10:21, 18 November 2013

2013-11-18T10:21:32Z

Brian: Created page with " // The following code for APIO 2010 "Commando" was contributed by Haidar Abboud. #include #include #include using names..."

2012-07-23T21:43:09Z

Created page with "<syntaxhighlight lang="cpp"> // The following code for APIO 2010 "Commando" was contributed by Haidar Abboud. #include <cstdio> #include <algorithm> #include <vector> using names..."

New page

<syntaxhighlight lang="cpp">
// The following code for APIO 2010 "Commando" was contributed by Haidar Abboud.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 1000001;
int N , a , b , c;
int x[MAXN];
long long sum[MAXN];
long long dp[MAXN];
// The convex hull trick code below was derived from acquire.cpp
vector <long long> M;
vector <long long> B;
bool bad(int l1,int l2,int l3)
{
return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]);
}
void add(long long m,long long b)
{
M.push_back(m);
B.push_back(b);
while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))
{
M.erase(M.end()-2);
B.erase(B.end()-2);
}
}
int pointer;
long long query(long long x)
{
if (pointer >M.size())
pointer=M.size()-1;
while (pointer<M.size()-1&&
M[pointer+1]*x+B[pointer+1]>M[pointer]*x+B[pointer])
pointer++;
return M[pointer]*x+B[pointer];
}

int main(){
scanf("%d" , &N);
scanf("%d %d %d" , &a , &b , &c);
for(int n = 1 ; n <= N ; n++){
scanf("%d" , &x[n]);
sum[n] = sum[n - 1] + x[n];
}
dp[1] = a * x[1] * x[1] + b * x[1] + c;
add(-2 * a * x[1] , dp[1] + a * x[1] * x[1] - b * x[1]);

for(int n = 2 ; n <= N ; n++){
dp[n] = a * sum[n] * sum[n] + b * sum[n] + c;
dp[n] = max(dp[n] , b * sum[n] + a * sum[n] * sum[n] + c + query(sum[n]));
add(-2 * a * sum[n] , dp[n] + a * sum[n] * sum[n] - b * sum[n]);
}
printf("%lld\n" , dp[N]);
return 0;
}
</syntaxhighlight>

@@ Line 1: / Line 1: @@
 <syntaxhighlight lang="cpp">
-// The following code for APIO 2010 "Commando" was contributed in Haidar Abboud.
+// The following code for APIO 2010 "Commando" was contributed by Haidar Abboud.
 #include <cstdio>
 #include <algorithm>

@@ Line 31: / Line 31: @@
 long long query(long long x)
+{
-         if (pointer >M.size())
+         if (pointer >=M.size())
                  pointer=M.size()-1;
          while (pointer<M.size()-1&&