제출 #162529

#제출 시각아이디문제언어결과실행 시간메모리
162529combi1k1수열 (APIO14_sequence)C++14
0 / 100
2067 ms3832 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define X first #define Y second const int N = 1e5 + 5; typedef pair<ll,ll> ii; struct ConvexHull { int tot, ptr; ii line[N]; int name[N]; int bad(ii a,ii b,ii c) { return 1.0 * (c.Y - a.Y) / (a.X - c.X) <= 1.0 * (b.Y - a.Y) / (a.X - b.X); } int add(ll s,ll c,int i){ while (tot > 1) { if (bad(line[tot - 1],line[tot],ii(s,c))) { tot--; continue; } break; } ++tot; line[tot] = ii(s,c); name[tot] = i; } ll get(int i,int x) { return line[i].X * x + line[i].Y; } ii get(int x) { for(ptr = min(ptr,tot) ; ptr < tot && get(ptr,x) <= get(ptr + 1,x) ; ++ptr); return ii(get(ptr,x),name[ptr]); } } Combi; int a[N], c[N]; ll f[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int k; cin >> k; for(int i = 1 ; i <= n ; ++i) cin >> a[i], a[i] += a[i - 1]; auto trial = [&](ll D) { Combi.tot = 0; Combi.ptr = 1; Combi.add(0,0,0); for(int i = 1 ; i <= n ; ++i) { int j = Combi.get(a[i] * 2).Y; f[i] = f[j] + 1ll * (a[i] - a[j]) * (a[i] - a[j]) - D; c[i] = c[j] + 1; Combi.add(a[i], -f[i] - 1ll * a[i] * a[i],i); } return c[n] > k; }; ll L = -1e13; ll R = 1e13; for(; L < R ;) { ll M = (L + R) / 2; if (trial(M)) R = M; else L = M + 1; } trial(L); ll ans = (1ll * a[n] * a[n] - f[n] - L * (k + 1)) / 2; cout << ans << "\n"; stack<int> res; for(int i = n - 1 ; i ; --i) if (f[i] + 1ll * (a[n] - a[i]) * (a[n] - a[i]) - L == f[n]) { n = i; res.push(i); } assert(res.size() == k); while (res.size()) cout << res.top() << " ", res.pop(); } /* 7 3 4 1 3 4 0 2 3 */

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

sequence.cpp: In member function 'int ConvexHull::add(long long int, long long int, int)':
sequence.cpp:33:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'int main()':
sequence.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(res.size() == k);
            ~~~~~~~~~~~^~~~
#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...