제출 #852125

#제출 시각아이디문제언어결과실행 시간메모리
852125chanhchuong123수열 (APIO14_sequence)C++14
0 / 100
67 ms131072 KiB
#include <bits/stdc++.h> using namespace std; #define task "" const long long INF = 1e18 + 0702; const int MAX = 100010; int n, k; int a[MAX]; long long pf[MAX]; int trace[MAX][202]; long long dp[MAX][202]; //struct Line { // long long m, c; int id; // // Line(long long _m = 0, long long _c = 0, int _id = 0) { // m = _m; // c = _c; // id = _id; // } // // long long eval(long long x) { // return m * x + c; // } // // double intersect(const Line &other) const { // return 1.0 * (c - other.c) / (other.m - m); // } //}; // //struct ConvexHullTrick { // vector<Line> lines; // int pt = 0; // // bool bad(const Line &l1, const Line &l2, const Line &l3) { // return l1.intersect(l3) <= l1.intersect(l2); // } // // void add(long long m, long long c, int id) { // Line line(m, c, id); while (lines.size() >= 2 && bad(lines[lines.size() - 2], lines.back(), line)) lines.pop_back(); // lines.push_back(line); pt = min(pt, int(lines.size()) - 1); // } // // pair<long long, int> get(long long x) { // if (lines.size() == 1) return make_pair(lines[0].eval(x), lines[0].id); while (pt + 1 < lines.size() && lines[pt + 1].eval(x) >= lines[pt].eval(x)) ++pt; // return make_pair(lines[pt].eval(x), lines[pt].id); // } //} cht[202]; struct Line { mutable long long m, b, p, id; bool operator<(const Line& o) const { return m < o.m; } bool operator<(long long x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) const long long inf = LLONG_MAX; long long div(long long a, long long b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return false; } if (x->m == y->m) x->p = x->b > y->b ? inf : -inf; else x->p = div(y->b - x->b, x->m - y->m); return x->p >= y->p; } void add(long long m, long long b, int id) { auto z = insert({m, b, 0, id}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } pair<long long, int> get(long long x) { assert(!empty()); auto l = *lower_bound(x); return make_pair(l.m * x + l.b, l.id); } } cht[202]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } cin >> n >> k; ++k; for (int i = 1; i <= n; ++i) { cin >> a[i]; pf[i] = pf[i - 1] + a[i]; } cht[0].add(0, 0, 0); for (int i = 1; i <= n; ++i) { for (int j = min(i, k); j >= 1; --j) { pair<long long, int> cur = cht[j - 1].get(pf[i]); trace[i][j] = cur.second; dp[i][j] = cur.first; cht[j].add(pf[i], - pf[i] * pf[i] + dp[i][j], i); } } cout << dp[n][k] << '\n'; vector<int> posAns; do { n = trace[n][k--]; posAns.push_back(n); } while (n > 1); for (int &id: posAns) { cout << id << ' '; } return 0; } /* 7 3 4 1 3 4 0 2 3 */

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

sequence.cpp: In function 'int main()':
sequence.cpp:85:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   freopen(task".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...