제출 #36740

#제출 시각아이디문제언어결과실행 시간메모리
36740junodeveloper수열 (APIO14_sequence)C++14
0 / 100
56 ms86676 KiB
#include "bits/stdc++.h" #define F first #define S second #define SZ(x) ((int)x.size()) using namespace std; template<class T> struct CHT { using pt = pair<T,T>; vector<pt> ln; vector<int> idx; int curr = 0; bool bad(pt& a, pt& b, T x) { return (b.S - a.S) >= x * (a.F - b.F); } bool bad(pt& a, pt& b, pt& c) { return (b.S - a.S) * (b.F - c.F) >= (c.S - b.S) * (a.F - b.F); } void insert(pt v, int i) { if(SZ(ln) > 0 && ln.back().F == v.F) { if(ln.back().S > v.S) return; else ln.pop_back(); } while(SZ(ln) >= 2 && bad(ln[SZ(ln)-2], ln.back(), v)) ln.pop_back(), idx.pop_back(); ln.push_back(v), idx.push_back(i); } pair<T, int> query(T x) { assert(SZ(ln) > 0); curr = min(curr, SZ(ln) - 1); while(curr < SZ(ln) - 1 && bad(ln[curr], ln[curr+1], x)) curr++; return {x * ln[curr].F + ln[curr].S, idx[curr]}; } void clear() { ln.clear(); idx.clear(); curr = 0; } }; int n, k, rec[100010][202]; long long s[100010], dp[100010], currDP; CHT<long long> cht; int main() { scanf("%d%d", &n, &k); for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1]; for(int j=2; j<=k+1; j++) { cht.clear(); cht.insert({s[j-1], dp[j-1] - s[j-1]*s[j-1]}, j-1); for(int i=j; i<=n; i++) { tie(currDP, rec[i][j]) = cht.query(s[i]); cht.insert({s[i], dp[i] - s[i]*s[i]}, i); dp[i] = currDP; } } printf("%lld\n", dp[n]); int p = n; vector<int> res; while(k > 0) { res.push_back(rec[p][k+1]); p = rec[p][k+1], k--; } for(int i=SZ(res)-1; i>=0; i--) printf("%d ", res[i]); return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:44:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:45:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; i++) scanf("%lld", s+i), s[i] += s[i-1];
                                                            ^
#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...