제출 #540463

#제출 시각아이디문제언어결과실행 시간메모리
540463dutinmeow수열 (APIO14_sequence)C++17
0 / 100
36 ms9612 KiB
#include <bits/stdc++.h> using namespace std; #pragma region debug #ifndef NDEBUG template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T1, typename T2, typename T3> ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) { return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')'; } template<typename T1, typename T2, typename T3, typename T4> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')'; } template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { os << '['; if (v.size()) { os << *v.begin(); for (auto i = ++v.begin(); i != v.end(); i++) os << ", " << (*i); } return os << ']'; } template<typename T, size_t N> ostream &operator<<(ostream &os, const array<T, N> &v) { os << '['; if (N) { os << *v.begin(); for (auto i = ++v.begin(); i != v.end(); i++) os << ", " << (*i); } return os << ']'; } template<typename T> ostream &operator<<(ostream &os, const set<T> &s) { os << '['; if (s.size()) { os << *s.begin(); for (auto i = ++s.begin(); i != s.end(); i++) os << ", " << (*i); } return os << ']'; } template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &s) { os << '['; if (s.size()) { os << *s.begin(); for (auto i = ++s.begin(); i != s.end(); i++) os << ", " << (*i); } return os << ']'; } template<typename T> ostream &operator<<(ostream &os, const multiset<T> &s) { os << '['; if (s.size()) { os << *s.begin(); for (auto i = ++s.begin(); i != s.end(); i++) os << ", " << (*i); } return os << ']'; } template<typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &s) { os << '['; if (s.size()) { os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')'; for (auto i = ++s.begin(); i != s.end(); i++) os << ", " << '(' << i->FF << " : " << i->SS << ')'; } return os << ']'; } template<typename T1, typename T2> ostream& operator<<(ostream& os, const unordered_map<T1, T2>& s) { os << '['; if (s.size()) { os << '(' << s.begin()->FF << " : " << s.begin()->SS << ')'; for (auto i = ++s.begin(); i != s.end(); i++) os << ", " << '(' << i->FF << " : " << i->SS << ')'; } return os << ']'; } #define dbg1(a) cerr << #a << " = " << a << '\n'; #define dbg2(a, b) dbg1(a) dbg1(b) #define dbg3(a, b, c) dbg1(a) dbg2(b, c) #define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d) #define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e) #define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f) #define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g) #define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h) #define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME #define dbg(...) get_dbg(__VA_ARGS__, dbg8, dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__) #else #define dbg(...) #endif #pragma endregion debug struct Line { long long m, b; Line(long long _m, long long _b) : m(_m), b(_b) {} long long operator()(long long x) { return m * x + b; } friend long double intersect(const Line &l1, const Line &l2) { return (long double)(l2.b - l1.b) / (long double)(l1.m - l2.m); } friend ostream& operator<<(ostream &os, const Line &l) { return os << '{' << l.m << "x + " << l.b << '}'; } }; int main() { int N, K; cin >> N >> K; vector<int> A(N + 1), P(N + 1, 0); for (int i = 1; i <= N; i++) { cin >> A[i]; P[i] = P[i - 1] + A[i]; } vector<vector<long long>> dp(K + 2, vector<long long>(N + 1, 0)); vector<vector<int>> par(K + 2, vector<int>(N + 1, 0)); for (int k = 1; k <= K + 1; k++) { deque<pair<Line, int>> dq; for (int i = 1; i <= N; i++) { Line l(P[i - 1], dp[k - 1][i - 1] - P[i - 1] * P[N]); while (dq.size() >= 2 && intersect(l, dq[dq.size() - 2].first) < intersect(l, dq[dq.size() - 1].first)) dq.pop_back(); dq.emplace_back(move(l), i - 1); while (dq.size() >= 2 && dq[0].first(P[i]) <= dq[1].first(P[i])) dq.pop_front(); dp[k][i] = dq[0].first(P[i]) + P[i] * P[N] - P[i] * P[i]; par[k][i] = dq[0].second; } } cout << dp[K + 1][N] << '\n'; vector<int> ans; for (int k = K + 1, c = N; k > 0; k--) { if (c != N) ans.push_back(c); c = par[k][c]; } reverse(ans.begin(), ans.end()); for (int c : ans) cout << c << ' '; cout << '\n'; /* cerr << "dp:\n"; for (int k = 1; k <= K + 1; k++) { dbg(dp[k]); } cerr << "par:\n"; for (int k = 1; k <= K + 1; k++) { dbg(par[k]); }*/ }

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

sequence.cpp:4: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
    4 | #pragma region debug
      | 
sequence.cpp:111: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
  111 | #pragma endregion debug
      |
#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...