제출 #42004

#제출 시각아이디문제언어결과실행 시간메모리
42004Aidyn_A수열 (APIO14_sequence)C++14
51 / 100
1828 ms83892 KiB
#include <stdio.h> #include <bits/stdc++.h> #define pb push_back #define pf push_front #define pp pop_back #define sz(a) (int)(a.size()) #define mp make_pair #define F first #define S second #define next _next #define prev _prev #define left _left #define right _right #define y1 _y1 #define all(x) x.begin(), x.end() #define what_is(x) #x << " is " << (x) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = (int)1e5 + 2; const ll INF = (ll)1e18 + 123; const int inf = (int)1e9 + 123; const int MOD = (int)1e9 + 7; const double eps = 1e-7; void megaRandom() { unsigned int FOR; asm("rdtsc" : "=A"(FOR)); srand(FOR); } struct line { ll k, b, ind; }; ld intersection(line a, line z) { if(a.k == z.k) return max(a.b, z.b); return (z.b - a.b) / (a.k - z.k); } vector<line> what; void add(line a) { while(sz(what) > 1 && intersection(what[sz(what) - 2], a) + eps <= intersection(what[sz(what) - 2], what.back())) what.pp(); what.pb(a); } int n, k; int a[N]; ll now[N], prev[N]; int pref[N]; int pr[202][N]; int main() { megaRandom(); cin >> n >> k; k ++; for(int i = 1; i <= n; i ++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } prev[0] = 0; int jt; for(int it = 1; it <= k; it ++) { memset(now, 0, sizeof now); what.clear(); jt = 0; if(it > 1) { for(int i = 1; i <= n; i ++) { ll val = 0; while(jt + 1 < sz(what) && intersection(what[jt], what[jt + 1]) + eps < pref[i]) jt ++; int j = i - 1; if(jt < sz(what)) j = what[jt].ind; //cout << "UNEXPECTED TURN!!!\n"; //return 0; j = min(j, i - 1); //assert(j <= i); now[i] = prev[j] + 1ll * pref[j] * (pref[i] - pref[j]); pr[it][i] = j; //cout << "it: " << it << " i: " << i << " j: " << j << "\n"; add({pref[i], prev[i] - (1ll * pref[i] * pref[i]), i}); } } for(int i = 1; i <= n; i ++) prev[i] = now[i]; } cout << prev[n] << "\n"; int x = k, y = n; vector<int> g; while(x > 1) { g.pb(pr[x][y]); y = pr[x][y], x --; } reverse(all(g)); for(int i = 0; i < sz(g); i ++) cout << g[i] << ' '; return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:79:8: warning: unused variable 'val' [-Wunused-variable]
     ll val = 0;
        ^
#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...