제출 #333775

#제출 시각아이디문제언어결과실행 시간메모리
333775Kamisama수열 (APIO14_sequence)C++14
11 / 100
2088 ms2000 KiB
#include <iostream> #include <cstdio> #define taskname "TEST" using namespace std; const int maxn = 1e4+3; const int maxk = 1e2+3; const long long inf = 1e18 + 7; struct TLines{ long long a, b; int id, nArr; inline TLines(long long _a = 0, long long _b = 0, int _id = 0, int _nArr = 0){ a=_a; b=_b; id=_id; nArr=_nArr; } inline long long Value(const long long &x){ return a*x+b; } friend inline bool isBad(const TLines &d1, const TLines &d2, const TLines &d3){ return (d2.b-d1.b)*(d1.a-d3.a)>=(d3.b-d1.b)*(d1.a-d2.a); } }; int n,k, a[maxn], trace[maxn]; long long s[maxn]; pair<long long, int> f[maxn]; TLines convex[maxn]; inline void Enter(){ cin >> n >> k; for(int i=1;i<=n;i++) cin >> a[i], s[i] = s[i-1] + a[i]; } inline pair<long long, int> Calc(const long long &C){ // f[i] = max{ s[j]*s[i] + f[j] - s[j]^2 } fill(f, f + n + 1, make_pair(0, 0)); fill(trace, trace + n + 1, -1); int best = 1, nConvex = 0; convex[++nConvex] = TLines(); f[1] = make_pair(s[1], 1); for(int i = 1; i <= n; i++){ long long x = s[i]; while(best < nConvex && convex[best].Value(x) <= convex[best + 1].Value(x)) best++; f[i].first = convex[best].Value(x) - C; f[i].second = convex[best].nArr + 1; trace[i] = convex[best].id; cerr << trace[i] << ' '; TLines newline(s[i], f[i].first - s[i] * s[i], i, f[i].second); while(nConvex > 1 && isBad(convex[nConvex - 1], convex[nConvex], newline)){ best -= (best == nConvex); nConvex--; } convex[++nConvex] = newline; } cerr << '\n'; return f[n]; // for(int t=1;t<=k;t++){ // int best=1; // int nConvex=0; // swap(f,g); // for(int i=1;i<=n;i++){ // long long x=s[i]; // TLines newline(s[i],g[i]-s[i]*s[i],i); // while(nConvex>1 && isBad(convex[nConvex-1],convex[nConvex],newline)){ // best-=(best==nConvex); // nConvex--; // } convex[++nConvex]=newline; // while(best<nConvex && convex[best].Value(x)<=convex[best+1].Value(x)) best++; // f[i]=convex[best].Value(x); // trace[i][t]=convex[best].id; // } // cerr << f[n] - g[n] << ' '; // } // cout<<f[n]<<'\n'; // int nG=0; // for(int x=n,i=k;i>=1;i--) g[++nG]=x=trace[x][i]; // for(int i=nG;i;i--) cout<<g[i]<<' '; } inline void Solve(){ long long l = 0, r = inf; while(l <= r){ long long mid = (l + r) >> 1; pair<long long, int> res = Calc(mid); if(res.second >= k + 1) l = mid + 1; else r = mid - 1; } cout << Calc(r).first + (k + 1) * r << '\n'; for(int i = trace[n]; i > 0; i = trace[i]) a[++s[0]] = i; for(int i = s[0]; i >= 1; i--) cout << a[i] << ' '; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); if(fopen(taskname".INP","r")) freopen(taskname".INP","r",stdin), freopen(taskname".OUT","w",stdout); Enter(); Solve(); return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:100:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  100 |     freopen(taskname".INP","r",stdin),
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:101:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  101 |     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...