제출 #1000704

#제출 시각아이디문제언어결과실행 시간메모리
1000704shenfe1수열 (APIO14_sequence)C++17
0 / 100
4 ms2000 KiB
#include <bits/stdc++.h> #define ll long long #define lb lower_bound #define pii pair<int,int> #define pll pair<ll,ll> #define F first #define S second #define ld long double #define pb push_back #define all(v) v.begin(),v.end() #define in insert #define sz(s) (int)s.size() #define int ll #define ppb pop_back using namespace std; const int MAX=1e5+10; const int inf=2e9; int n,k; int a[MAX]; int dp[MAX][211]; int pr[MAX][211]; int p[MAX]; // struct CHT{ // vector<pii> vec; // vector<int> num; // int pos; // void init(){ // pos=0; // vec.clear(); // num.clear(); // } // ld inter(pii a,pii b){ // // cout<<b.F<<" "<<a.F<<"\n"; // return (0.0+a.S-b.S)/(b.F-a.F); // } // void add(int k,int x,int i){ // // cout<<k<<" "<<x<<"\n"; // while(!vec.empty()&&vec.back().F==k){ // if(vec.back().S<x){ // vec.ppb(); // num.ppb(); // } // else{ // return; // } // } // while(sz(vec)>=2&&inter(vec.back(),vec[sz(vec)-2])>=inter(vec[sz(vec)-2],{k,x})){ // vec.ppb(); // num.ppb(); // } // vec.pb({k,x}); // num.pb(i); // pos=min(pos,sz(vec)-1); // } // int get(pii a,int x){ // return a.F*x+a.S; // } // int get(int X){ // while(pos+1<sz(vec)&&get(vec[pos],X)<=get(vec[pos+1],X))pos++; // return get(vec[pos],X); // } // }C; void solve(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ p[i]=p[i-1]+a[i]; } // for(int K=2;K<=k+1;K++){ // C.init(); // for(int i=K;i<=n;i++){ // C.add(p[i-1],dp[i-1][K-1]-p[i-1]*p[i-1],i-1); // dp[i][K]=C.get(p[i]); // pr[i][K]=C.num[C.pos]; // // cout<<i<<" "<<K<<" "<<pr[i][K]<<"\n"; // } // } // cout<<dp[n][k+1]<<"\n"; // vector<int> ans; // int cur=n; // while(k>=0){ // ans.pb(cur); // cur=pr[cur][(k+1)]; // k--; // } // sort(all(ans)); // ans.ppb(); // for(int x:ans){ // cout<<x; // if(x!=ans.back())cout<<" "; // } } // #ifdef LOCAL signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; // cin>>t; while(t--)solve(); } // #endif
#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...