제출 #926418

#제출 시각아이디문제언어결과실행 시간메모리
926418idiotcomputer수열 (APIO14_sequence)C++11
0 / 100
20 ms5772 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int #define pii pair<ll,ll> #define f first #define s second //a + (x-c)^2 > b + (x-c2)^2 // a + c^2-2cx > b + c2^2 - 2c2x //a - b + c^2 - c2^2 > 2x * (c-c2) //b - a + c2^2 - c^2 < 2x * (c2-c) double find(ll a, ll b, ll c1, ll c2){ return (double) (b-a+c2*c2-c1*c1) / (double) (2*(c2-c1)); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin >> n >> k; ll vals[n]; ll psum[n]; for (int i =0; i < n; i++){ cin >> vals[i]; psum[i] = vals[i]; if (i>0) psum[i] += psum[i-1]; } ll tot = psum[n-1]*psum[n-1]; int past[n][k+2]; // idx, val vector<deque<pii>> all(k+1); ll cval; for (int i =0; i < n; i++){ // cout << i << ":\n"; cval = psum[i]*psum[i]; for (int j =0; j < k; j++){ // cout << j+1 << "," << cval << " : "; int t = all[j].size(); while (t >= 2 && find(all[j][0].s,all[j][1].s,psum[all[j][0].f],psum[all[j][1].f]) <= (double) psum[i]){ all[j].pop_front(); t -= 1; } while (t >= 2 && find(all[j][t-2].s,all[j][t-1].s,psum[all[j][t-2].f],psum[all[j][t-1].f]) <= find(all[j][t-1].s,cval,psum[all[j][t-1].f],psum[i])){ all[j].pop_back(); t -= 1; } all[j].push_back({i,cval}); /* for (int k = 0; k < all[j].size(); k++){ cout << all[j][k].f << "," << all[j][k].s << " "; } cout << '\n';*/ if (t != 0){ //cout << all[j][0].f << ',' << all[j][0].s << ' '; past[i][j+1] = all[j][0].f; cval = all[j][0].s + (psum[i] - psum[all[j][0].f]) * (psum[i] - psum[all[j][0].f]); } else { break; } } // cout << '\n'; } tot -= cval; // cout << cval << '\n'; cout << tot/2 << '\n'; int curr = all[k-1][0].f; int t = k; while (t > 0){ cout << curr+1 << " "; t--; curr = past[curr][t]; } cout << '\n'; return 0; } /* 7 3 4 1 3 4 0 2 3 */

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

sequence.cpp: In function 'int main()':
sequence.cpp:69:9: warning: 'cval' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     tot -= cval;
      |     ~~~~^~~~~~~
#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...