Submission #367517

#TimeUsernameProblemLanguageResultExecution timeMemory
367517arnold518Split the sequence (APIO14_sequence)C++14
0 / 100
324 ms7324 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; int N, K; ll A[MAXN+10]; struct Line { ll a, b; int p; }; double cross(Line p, Line q) { return (double)(p.b-q.b)/(q.a-p.a); } struct CHT { vector<Line> S; void init() { S.clear(); } void update(Line p) { if(!S.empty() && S.back().a==p.a) { if(S.back().b<=p.b) return; S.pop_back(); } while(S.size()>1 && cross(S[S.size()-2], S[S.size()-1])>=cross(S[S.size()-1], p)) S.pop_back(); S.push_back(p); } int query(ll x) { int lo=0, hi=S.size(); while(lo+1<hi) { int mid=lo+hi>>1; if(cross(S[mid], S[mid-1])<=x) lo=mid; else hi=mid; } return S[lo].p; } }cht; pll dp[MAXN+10]; int memo[MAXN+10]; vector<int> V, ansV; pll solve(ll lambda) { cht.init(); cht.update({0, 0, 0}); V.clear(); for(int i=1; i<=N; i++) { int t=cht.query(A[i]); dp[i].first=dp[t].first+(A[i]-A[t])*(A[i]-A[t])*2+lambda; dp[i].second=dp[t].second+1; memo[i]=t; cht.update({-2*A[i], A[i]*A[i]+dp[i].first, i}); } for(int i=N; i>0;) { V.push_back(i); i=memo[i]; } V.push_back(0); reverse(V.begin(), V.end()); assert(V.size()==dp[N].second+1); //printf("%lld : %lld %lld\n", lambda, dp[N].first, dp[N].second); return dp[N]; } int main() { scanf("%d%d", &N, &K); K++; for(int i=1; i<=N; i++) scanf("%lld", &A[i]); for(int i=1; i<=N; i++) A[i]+=A[i-1]; ll lo=0, hi=1e9; while(lo+1<hi) { ll mid=lo+hi>>1; if(solve(2*mid+1).second<K) hi=mid; else lo=mid; } vector<int> L, R; solve(2*hi+1); L=V; assert(L.size()==dp[N].second+1); solve(2*lo+1); R=V; assert(R.size()==dp[N].second+1); if(L.size()-1==K) { ansV=L; } else if(R.size()-1==K) { ansV=R; } else { assert(L.size()<K && K<R.size()); for(int i=0; i+1<R.size(); i++) { int l=R[i], r=R[i+1]; int lt=upper_bound(L.begin(), L.end(), l)-L.begin()-1; if(L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K) { for(int j=0; j<=i; j++) ansV.push_back(R[j]); for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]); break; } } } ll ans=solve(2*hi).first/2-hi*K; ans=(A[N]*A[N]-ans)/2; printf("%lld\n", ans); for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]); printf("\n"); }

Compilation message (stderr)

sequence.cpp: In member function 'int CHT::query(ll)':
sequence.cpp:42:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |    int mid=lo+hi>>1;
      |            ~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'pll solve(ll)':
sequence.cpp:73:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   73 |  assert(V.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   ll mid=lo+hi>>1;
      |          ~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:95:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   95 |  assert(L.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:97:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   97 |  assert(R.size()==dp[N].second+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:99:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |  if(L.size()-1==K)
      |     ~~~~~~~~~~^~~
sequence.cpp:103:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  else if(R.size()-1==K)
      |          ~~~~~~~~~~^~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp:109:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |   assert(L.size()<K && K<R.size());
      |          ~~~~~~~~^~
sequence.cpp:109:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   assert(L.size()<K && K<R.size());
      |                        ~^~~~~~~~~
sequence.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i=0; i+1<R.size(); i++)
      |                ~~~^~~~~~~~~
sequence.cpp:114:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  114 |    if(L[lt]<=l && r<=L[lt+1] && i+L.size()-lt-1==K)
      |                                 ~~~~~~~~~~~~~~~^~~
sequence.cpp:117:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for(int j=lt+1; j<L.size(); j++) ansV.push_back(L[j]);
      |                     ~^~~~~~~~~
sequence.cpp:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |  for(int i=1; i+1<ansV.size(); i++) printf("%d ", ansV[i]);
      |               ~~~^~~~~~~~~~~~
sequence.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |  scanf("%d%d", &N, &K); K++;
      |  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  for(int i=1; i<=N; i++) scanf("%lld", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
#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...