제출 #1086528

#제출 시각아이디문제언어결과실행 시간메모리
1086528User0069수열 (APIO14_sequence)C++17
71 / 100
54 ms131072 KiB
#include<bits/stdc++.h> #define taskname "" #define el '\n' #define fi first #define sc second #define pii pair<int, int> #define all(v) v.begin(), v.end() #define int long long using namespace std; #define Faster ios_base::sync_with_stdio(false);cin.tie(0); const int maxn=1e5+33; const int N=1e5; const int mod=1e9+7; const long long INF=1e18+2; int n,k,a[maxn],dp[maxn][202],trace[maxn][202]; struct line { int a,b,i; }; vector<line> cht; vector<long double> point; long double intersect(line x,line y) { return 1.0*(y.b-x.b)/(x.a-y.a); } void pop() { cht.pop_back(),point.pop_back(); } void add(line x) { while(cht.size()&&cht.back().a==x.a) pop(); while(cht.size()>1&&intersect(x,cht.back())<=point.back()) pop(); if(cht.size()) point.push_back(intersect(x,cht.back())); else point.push_back(-INF); cht.push_back(x); } signed main() { if (fopen(taskname".INP","r")) { freopen(taskname".INP","r",stdin); freopen(taskname".OUT","w",stdout); } Faster cin>>n>>k; k++; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]+=a[i-1]; } for(int i=2;i<=k;i++) { cht.clear(); point.clear(); add({a[i-1],dp[i-1][i-1]-a[i-1]*a[i-1],i-1}); int ii=0; for(int j=i;j<=n;j++) { while(ii+1<cht.size()&&point[ii+1]<a[j]) ii++; dp[j][i]=cht[ii].a*a[j]+cht[ii].b; trace[j][i]=cht[ii].i; add({a[j],dp[j][i-1]-a[j]*a[j],j}); } } cout<<dp[n][k]<<"\n"; int siu=n; for(int i=k;i>1;i--) { cout<<trace[siu][i]<<" "; siu=trace[siu][i]; } // cout<<"\n"; // for(int i=1;i<=n;i++) // { // for(int j=1;j<=k;j++) // { // cout<<dp[i][j]<<" "; // } // cout<<"\n"; // } }

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

sequence.cpp: In function 'int main()':
sequence.cpp:61:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             while(ii+1<cht.size()&&point[ii+1]<a[j]) ii++;
      |                   ~~~~^~~~~~~~~~~
sequence.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...