제출 #976102

#제출 시각아이디문제언어결과실행 시간메모리
976102nnin수열 (APIO14_sequence)C++17
0 / 100
17 ms2652 KiB
#include<bits/stdc++.h> using namespace std; int n, k; long long arr[100005]; long long sum[100005]; double a[100005]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n;i++) { cin>>a[i]; a[i] += a[i-1]; } double part = a[n]/(k+1); vector<int> idx; idx.push_back(0); for(int i=1;i<=k;i++) { int it = lower_bound(a+1+idx[i-1], a+1+n, a[idx[i-1]]+part)-a; if(it==idx[i-1]+1 || a[it]-a[idx[i-1]]-part < part-a[it-1]+a[idx[i-1]]) { idx.push_back(it); } else { idx.push_back(it-1); } part = (a[n]-a[idx[i]])/(k+1-i); } idx.push_back(n); for(int i=1;i<=k+1;i++) { arr[i-1] = (long long)a[idx[i]]-(long long)a[idx[i-1]]; } for(int i=k;i>=0;i--) { sum[i] = sum[i+1]+arr[i]; } long long ans = 0; for(int i=0;i<=k;i++) { ans += arr[i]*sum[i+1]; } cout<<ans<<'\n'; for(int i=1;i<=k;i++) cout<<idx[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...