https://wcipeg.com/wiki/index.php?title=Convex_hull_trick/commando.cpp&feed=atom&action=history
Convex hull trick/commando.cpp - Revision history
2024-03-29T05:29:26Z
Revision history for this page on the wiki
MediaWiki 1.25.2
https://wcipeg.com/wiki/index.php?title=Convex_hull_trick/commando.cpp&diff=1963&oldid=prev
101.60.169.14 at 14:31, 11 March 2016
2016-03-11T14:31:46Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 14:31, 11 March 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="cpp"></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="cpp"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>// The following code for APIO 2010 "Commando" was contributed <del class="diffchange diffchange-inline">in </del>Haidar Abboud.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>// The following code for APIO 2010 "Commando" was contributed <ins class="diffchange diffchange-inline">by </ins>Haidar Abboud.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <cstdio></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <cstdio></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <algorithm></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <algorithm></div></td></tr>
</table>
101.60.169.14
https://wcipeg.com/wiki/index.php?title=Convex_hull_trick/commando.cpp&diff=1962&oldid=prev
101.60.169.14 at 14:29, 11 March 2016
2016-03-11T14:29:44Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 14:29, 11 March 2016</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="cpp"></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><syntaxhighlight lang="cpp"></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>// The following code for APIO 2010 "Commando" was contributed <del class="diffchange diffchange-inline">by </del>Haidar Abboud.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>// The following code for APIO 2010 "Commando" was contributed <ins class="diffchange diffchange-inline">in </ins>Haidar Abboud.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <cstdio></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <cstdio></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <algorithm></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>#include <algorithm></div></td></tr>
</table>
101.60.169.14
https://wcipeg.com/wiki/index.php?title=Convex_hull_trick/commando.cpp&diff=1752&oldid=prev
180.211.180.26 at 10:21, 18 November 2013
2013-11-18T10:21:32Z
<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 10:21, 18 November 2013</td>
</tr><tr><td colspan="2" class="diff-lineno" id="L31" >Line 31:</td>
<td colspan="2" class="diff-lineno">Line 31:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>long long query(long long x)</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>long long query(long long x)</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>         if (pointer >M.size())</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>         if (pointer ><ins class="diffchange diffchange-inline">=</ins>M.size())</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                 pointer=M.size()-1;</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>                 pointer=M.size()-1;</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>         while (pointer<M.size()-1&&</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>         while (pointer<M.size()-1&&</div></td></tr>
</table>
180.211.180.26
https://wcipeg.com/wiki/index.php?title=Convex_hull_trick/commando.cpp&diff=1670&oldid=prev
Brian: 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..."
2012-07-23T21:43:09Z
<p>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..."</p>
<p><b>New page</b></p><div><syntaxhighlight lang="cpp"><br />
// The following code for APIO 2010 "Commando" was contributed by Haidar Abboud.<br />
#include <cstdio><br />
#include <algorithm><br />
#include <vector><br />
using namespace std;<br />
<br />
const int MAXN = 1000001;<br />
int N , a , b , c;<br />
int x[MAXN];<br />
long long sum[MAXN];<br />
long long dp[MAXN];<br />
// The convex hull trick code below was derived from acquire.cpp<br />
vector <long long> M;<br />
vector <long long> B;<br />
bool bad(int l1,int l2,int l3)<br />
{<br />
return (B[l3]-B[l1])*(M[l1]-M[l2])<(B[l2]-B[l1])*(M[l1]-M[l3]);<br />
}<br />
void add(long long m,long long b)<br />
{<br />
M.push_back(m);<br />
B.push_back(b);<br />
while (M.size()>=3&&bad(M.size()-3,M.size()-2,M.size()-1))<br />
{<br />
M.erase(M.end()-2);<br />
B.erase(B.end()-2);<br />
}<br />
}<br />
int pointer;<br />
long long query(long long x)<br />
{<br />
if (pointer >M.size())<br />
pointer=M.size()-1;<br />
while (pointer<M.size()-1&&<br />
M[pointer+1]*x+B[pointer+1]>M[pointer]*x+B[pointer])<br />
pointer++;<br />
return M[pointer]*x+B[pointer];<br />
}<br />
<br />
int main(){<br />
scanf("%d" , &N);<br />
scanf("%d %d %d" , &a , &b , &c);<br />
for(int n = 1 ; n <= N ; n++){<br />
scanf("%d" , &x[n]);<br />
sum[n] = sum[n - 1] + x[n];<br />
}<br />
dp[1] = a * x[1] * x[1] + b * x[1] + c;<br />
add(-2 * a * x[1] , dp[1] + a * x[1] * x[1] - b * x[1]);<br />
<br />
for(int n = 2 ; n <= N ; n++){<br />
dp[n] = a * sum[n] * sum[n] + b * sum[n] + c;<br />
dp[n] = max(dp[n] , b * sum[n] + a * sum[n] * sum[n] + c + query(sum[n]));<br />
add(-2 * a * sum[n] , dp[n] + a * sum[n] * sum[n] - b * sum[n]);<br />
}<br />
printf("%lld\n" , dp[N]);<br />
return 0;<br />
}<br />
</syntaxhighlight></div>
Brian