Submission #48169

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
481692018-05-10 12:21:55tmwilliamlin168Split the sequence (APIO14_sequence)C++14
100 / 100
892 ms84280 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=1e5;
int n, k, prv[201][mxN+1], qh, qt;
ll ps[mxN+1], dp[2][mxN+1], a[mxN+1], b[mxN+1], c[mxN+1];
inline void al(ll ai, ll bi, ll ci) {
if(qt-qh>=1&&a[qt-1]==ai) {
if(bi<b[qt-1])
--qt;
else
return;
}
while(qt-qh>=2&&(b[qt-1]-b[qt-2])/(a[qt-2]-a[qt-1])>=(bi-b[qt-1])/(a[qt-1]-ai))
--qt;
a[qt]=ai;
b[qt]=bi;
c[qt]=ci;
++qt;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i=0; i<n; ++i)
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:36:32: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   al(-2*ps[i], ps[i]*ps[i]+dp[i&1^1][i], i);
                               ~^~
sequence.cpp:42:33: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    al(-2*ps[j], ps[j]*ps[j]+dp[i&1^1][j], j);
                                ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...