제출 #406795

#제출 시각아이디문제언어결과실행 시간메모리
406795JerryLiu06수열 (APIO14_sequence)C++17
71 / 100
65 ms131076 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vd = vector<db>; using vs = vector<str>; using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; #define mp make_pair #define f first #define s second #define sz(x) (int)(x).size() #define bg(x) begin(x) #define all(x) bg(x), end(x) #define sor(x) sort(all(x)) #define ft front() #define bk back() #define pb push_back #define pf push_front #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define R0F(i, a) ROF(i, 0, a) #define EACH(a, x) for (auto& a : x) const int MOD = 1e9 + 7; const int MX = 1e6 + 1; const int MXN = 1e5 + 1; const int MXK = 201; const ll INF = 1e18; int N, K; ll S[MXN], DP[MXN][2], ans[MXN][MXK]; int Q[MX], L = 1, R = 1; bool check1(int A, int B, int i, int j) { return S[A] * S[A] + DP[A][j] - S[B] * S[B] - DP[B][j] >= S[i] * (2 * S[A] - 2 * S[B]); } bool check2(int A, int B, int i, int j) { return (S[A] * S[A] + DP[A][j] - S[B] * S[B] - DP[B][j]) * (2 * S[B] - 2 * S[i]) >= (S[B] * S[B] + DP[B][j] - S[i] * S[i] - DP[i][j]) * (2 * S[A] - 2 * S[B]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> K; FOR(i, 1, N + 1) { int A; cin >> A; S[i] = A + S[i - 1]; } FOR(i, 1, N + 1) DP[i][1] = S[i] * S[i]; FOR(j, 2, K + 2) { L = R = 1; Q[R++] = 0; FOR(i, 1, N + 1) { while (R - L > 1 && check1(Q[L], Q[L + 1], i, (j - 1) % 2)) L++; int cur = Q[L]; DP[i][j % 2] = DP[cur][(j - 1) % 2] + (S[i] - S[cur]) * (S[i] - S[cur]); ans[i][j] = cur; while (R - L > 1 && check2(Q[R - 2], Q[R - 1], i, (j - 1) % 2)) R--; Q[R++] = i; } } cout << (S[N] * S[N] - DP[N][(K + 1) % 2]) / 2 << "\n"; int ind = N; ROF(i, 2, K + 2) { ind = ans[ind][i]; cout << (!ind ? 1 : ind) << " "; } }

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

sequence.cpp: In function 'int main()':
sequence.cpp:73:13: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   73 |             while (R - L > 1 && check2(Q[R - 2], Q[R - 1], i, (j - 1) % 2)) R--; Q[R++] = i;
      |             ^~~~~
sequence.cpp:73:82: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   73 |             while (R - L > 1 && check2(Q[R - 2], Q[R - 1], i, (j - 1) % 2)) R--; Q[R++] = i;
      |                                                                                  ^
#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...