제출 #994995

#제출 시각아이디문제언어결과실행 시간메모리
994995Baytoro수열 (APIO14_sequence)C++17
0 / 100
58 ms82672 KiB
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second #define pb push_back //#define int long long #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() void fopn(string name){ freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout); } #define ll long long const int N=1e5+5; int n; struct line{ ll m, b; ll operator *(int x){ return m*x+b; } int operator ^(line x){ return ceil((b-x.b)/(x.m-m)); } }; struct CHT{ deque<int64_t> a, b; deque<int> c; void init() { a.clear(); b.clear(); c.clear(); } void push(int64_t n, int64_t m, int v) { while (a.size() > 1 && (b[b.size() - 2] - b.back()) * (n - a.back()) >= (b.back() - m) * (a.back() - a[a.size() - 2])) { a.pop_back(); b.pop_back(); c.pop_back(); } a.push_back(n); b.push_back(m); c.push_back(v); } pair<int64_t, int> query(int64_t x) { while (a.size() > 1 && (a[1] - a[0]) * x > (b[0] - b[1])) { a.pop_front(); b.pop_front(); c.pop_front(); } return make_pair(a[0] * x + b[0], c[0]); } }; vector<int> dp_cur(N),dp_prev(N); int p[N][205]; void solve(){ int n,k;cin>>n>>k; vector<int> a(n+1),pref(n+1); for(int i=0;i<n;i++){ cin>>a[i]; pref[i+1]=a[i]+pref[i]; } for(int i=0;i<n-1;i++){ dp_prev[i]=pref[i+1]*(pref[n]-pref[i+1]); p[i][1]=-1; } for(int j=2;j<=k;j++){ CHT cht; dp_cur[0]=0; for(int i=1;i<n-1;i++){ cht.push(pref[i],dp_prev[i-1],i); auto it=cht.query(pref[i+1]-pref[n]); dp_cur[i]=it.fr+pref[i+1]*pref[n]-pref[i+1]*pref[i+1]; p[i][j]=it.sc-1; } dp_prev=dp_cur; } int ans=0,c=0; for(int i=0;i<n-1;i++){ if(ans<dp_prev[i]){ ans=dp_prev[i]; c=i; } } cout<<ans<<endl; for(int i=0;i<k;i++){ cout<<c+1<<' '; c=p[c][k-i]; } } signed main(){ //fopn("paint"); int t=1;//cin>>t; while(t--) solve(); }

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

sequence.cpp: In function 'void fopn(std::string)':
sequence.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:11:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  freopen((name+".out").c_str(),"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...