제출 #212757

#제출 시각아이디문제언어결과실행 시간메모리
212757kig9981수열 (APIO14_sequence)C++17
0 / 100
15 ms3580 KiB
#include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; long long D[2][100001]; int N, PS[100001], P[200][100001]; double cross(int a, int b, int k) { return 1.*(1LL*PS[a]*PS[a]-1LL*PS[b]*PS[b]+D[k&1][b]-D[k&1][a])/(PS[a]-PS[b]); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); TEST(freopen("input.txt","r",stdin)); TEST(freopen("output.txt","w",stdout)); TEST(freopen("debug.txt","w",stderr)); int K, j; vector<int> idx; cin>>N>>K; for(int i=1;i<=N;i++) { cin>>PS[i]; PS[i]+=PS[i-1]; } for(int k=1;k<K;k++) { idx.clear(); idx.push_back(k); j=0; for(int i=k+1;i<=N;i++) { while(j+1<idx.size() && cross(idx[j],idx[j+1],k-1)-1e-9<=PS[i]) j++; D[k&1][i]=(PS[i]-PS[idx[j]])*PS[idx[j]]+D[~k&1][idx[j]]; P[k][i]=idx[j]; while(idx.size()>1 && cross(idx[idx.size()-2],idx.back(),k-1)>cross(idx.back(),i,k-1)) idx.pop_back(); idx.push_back(i); } } idx.clear(); j=K; for(int i=K+1;i<N;i++) if(1LL*(PS[N]-PS[i])*PS[i]+D[~K&1][i]>=1LL*(PS[N]-PS[j])*PS[j]+D[~K&1][j]) j=i; cout<<1LL*(PS[N]-PS[j])*PS[j]+D[~K&1][j]<<'\n'; for(int k=K-1;k>=0;k--) { idx.push_back(j); j=P[k][j]; } reverse(idx.begin(),idx.end()); for(auto a: idx) cout<<a<<' '; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int main()':
sequence.cpp:37:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j+1<idx.size() && cross(idx[j],idx[j+1],k-1)-1e-9<=PS[i]) 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...