제출 #928770

#제출 시각아이디문제언어결과실행 시간메모리
928770Foolestboy수열 (APIO14_sequence)C++14
71 / 100
40 ms131072 KiB
#include <bits/stdc++.h> #define SQR(x) (1LL * ((x) * (x))) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define fi first #define se second #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define sz(s) (int)s.size() #define prev __prev #define next __next #define left __left #define right __right #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vll vector<ll> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef unsigned int ui; using namespace std; const int mod = 1e9 + 7; const int INF = 1e9 + 7; const ll INFLL = (ll)2e18 + 7LL; const ld PI = acos(-1); const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1}; const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; template<class BUI, class TRONG> bool minimize(BUI &x, const TRONG y){ if(x > y){ x = y; return true; } else return false; } template<class BUI, class TRONG> bool maximize(BUI &x, const TRONG y){ if(x < y){ x = y; return true; } else return false; } /* Author : Bui Nguyen Duc Trong, Luong Van Chanh High School for the gifted*/ /* Template is copied by Trong */ /** Losing in Provincial Contests **/ /** TRYING HARDER**/ /** ORZ **/ /* -----------------[ MAIN CODE GOES HERE ]----------------- */ mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e5 + 10; int n, k; int a[N]; struct Line{ ll a, b; Line() : a(0), b(0) {} Line(ll a, ll b) : a(a), b(b) {} ll f(ll x) { return a * x + b; } }; struct ConvexHullTrick{ vector<Line> vec; int iter = 0; void reset(){ vec.clear(); iter = 0; } ld inter(Line A, Line B){ return (ld)(A.b - B.b) / (B.a - A.a); } void insertLine(Line l){ if(!vec.empty() && l.a == vec.back().a) maximize(vec.back().b, l.b); else{ while(sz(vec) >= 2 && inter(l, vec.back()) <= inter(vec.back(), vec[sz(vec) - 2])) vec.pop_back(); vec.push_back(l); } } ll query(ll x){ minimize(iter, sz(vec) - 1); while(iter + 1 < sz(vec) && vec[iter + 1].f(x) >= vec[iter].f(x)) ++iter; return vec[iter].f(x); } } cht; ll f[N][202]; void solve(){ cin >> n >> k; for(int i = 1; i <= n; i++){ cin >> a[i]; a[i] += a[i - 1]; } for(int j = 1; j <= k; j++){ cht.reset(); for(int i = 1; i <= n; i++){ cht.insertLine(Line(a[i - 1], f[i - 1][j - 1] - 1LL * a[i - 1] * a[i - 1])); f[i][j] = cht.query(a[i]); } } int r = n; vector<int> ans; for(int i = k; i >= 1; i--){ bool found = 0; for(int j = r; j >= 2; j--){ if(f[j - 1][i - 1] + 1LL * (a[r] - a[j - 1]) * a[j - 1] == f[r][i]){ ans.push_back(j - 1); r = j - 1; found = 1; break; } } assert(found); } cout << f[n][k] << '\n'; reverse(all(ans)); for(int x : ans) cout << x << ' '; cout << '\n'; } /* 7 3 4 1 3 4 0 2 3 */ signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); const bool multitest = 0; int tt = 1; if(multitest) cin >> tt; while( tt-- ){ solve(); } return 0; }

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

sequence.cpp: In function 'void solve()':
sequence.cpp:139:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  139 |     for(int x : ans) cout << x << ' '; cout << '\n';
      |     ^~~
sequence.cpp:139:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  139 |     for(int x : ans) cout << x << ' '; cout << '\n';
      |                                        ^~~~
#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...