Submission #101021

#TimeUsernameProblemLanguageResultExecution timeMemory
101021Retro3014Split the sequence (APIO14_sequence)C++17
0 / 100
407 ms132096 KiB
#include <bits/stdc++.h> #define pb push_back #define all(v) ((v).begin(), (v).end()) #define sortv(v) sort(all(v)) #define sz(v) ((int)(v).size()) #define uniqv(v) (v).erase(unique(all(v)), (v).end()) #define umax(a, b) (a)=max((a), (b)) #define umin(a, b) (a)=min((a), (b)) #define FOR(i,a,b) for(int i = (a); i <= (b); i++) #define rep(i,n) FOR(i,1,n) #define rep0(i,n) FOR(i,0,(int)(n)-1) #define FI first #define SE second #define INF 2000000000 #define INFLL 1000000000000000000LL using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef long double ld; const int MAX_N = 100010; const int MAX_K = 210; int N, K; vector<ll> v; ll S[MAX_N+1]; ll dp[MAX_K+1][MAX_N+1]; int from[MAX_K+1][MAX_N+1]; pll pr[MAX_N+1]; vector<int> st; int k; ll calc(int x, int y){ pll tmp = {S[x], dp[k-1][x] - S[x]*S[x]}; return tmp.first * S[y] + tmp.second; } bool chk(int x){ ld x1 = -(ld)(pr[x].second - pr[st.back()].second) / (ld)(pr[x].first - pr[st.back()].first); ld x2 = -(ld)(pr[st.back()].second - pr[st[st.size()-2]].second) / (ld)(pr[st.back()].first - pr[st[st.size()-2]].first); if(x1<=x2) return true; return false; } int main(){ scanf("%d%d", &N, &K); v.push_back(0); for(int i=1; i<=N; i++){ ll x; scanf("%lld", &x); v.push_back(x); S[i] = S[i-1] + v[i]; } int idx = 0; for(k=1; k<=K; k++){ idx = 0; st.clear(); st.pb(1); pr[k] = {S[k], dp[k-1][k] - S[k]*S[k]}; for(int i=k+1; i<=N; i++){ while(st.size() > idx + 1 && calc(st[idx], i) < calc(st[idx+1], i)) idx++; dp[k][i] = calc(st[idx], i); from[k][i] = st[idx]; pr[i] = {S[i], dp[k-1][i] - S[i]*S[i]}; if(pr[i].first==pr[st.back()].first){ if(pr[i].second>pr[st.back()].second){ if(idx==st.size()-1) idx--; st.pop_back(); }else{ continue; } } while(st.size()>1 && chk(i)){ if(idx==st.size()-1) idx--; st.pop_back(); } st.push_back(i); idx = max(idx, 0); //cout<<k<<" "<<i<<" "<<dp[k][i]<<" "<<from[k][i]<<endl; } } printf("%lld\n", dp[K][N]); vector<int> ans; idx = N; while(K>=1){ idx = from[K][idx]; K--; ans.pb(idx); } while(!ans.empty()){ printf("%d ", ans.back()); ans.pop_back(); } return 0; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(st.size() > idx + 1 && calc(st[idx], i) < calc(st[idx+1], i)) idx++;
          ~~~~~~~~~~^~~~~~~~~
sequence.cpp:66:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(idx==st.size()-1) idx--;
         ~~~^~~~~~~~~~~~~
sequence.cpp:73:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx==st.size()-1) idx--;
        ~~~^~~~~~~~~~~~~
sequence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x); v.push_back(x);
         ~~~~~^~~~~~~~~~~~
#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...