제출 #42041

#제출 시각아이디문제언어결과실행 시간메모리
42041OneSubmissionMan수열 (APIO14_sequence)C++11
71 / 100
2063 ms84200 KiB
# include <bits/stdc++.h> # define F first # define S second # define mp make_pair // everything go according to my plan # define pb push_back # define sz(a) (int)(a.size()) # define vec vector // shimkenttin kyzdary, dzyn, dzyn, dzyn... # define y1 Y_U_NO_y1 # define left Y_U_NO_left # define right Y_U_NO_right using namespace std; typedef pair <int, int> pii; typedef long long ll; typedef long double ld; const int Mod = (int)1e9 + 7; const int MX = 1073741822; const ll MXLL = 4e18; const int Sz = 1110111; // a pinch of soul inline void Read_rap () { ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); } inline void randomizer3000 () { unsigned int seed; asm ("rdtsc" : "=A"(seed)); srand (seed); } void files (string problem) { if (fopen ((problem + ".in").c_str(),"r")) { freopen ((problem + ".in").c_str(),"r",stdin); freopen ((problem + ".out").c_str(),"w",stdout); } } void localInput (string in = "s") { if (fopen (in.c_str(), "r")) freopen (in.c_str(), "r", stdin); else { cerr << "Input file not found" << endl; } } const int K = 200 + 1; const int N = 1e5 + 1; int n; int k; ll pref[Sz]; int a[Sz]; int pr[K][N]; const double eps = 1e-12; struct CHT { struct line { ll k, b; ll get (ll x) { return k * x + b; } }; vec<line> r; vec<int> id; int ptr; CHT() : ptr(0) {} void clear() { r.clear(); id.clear(); ptr = 0; } ld intersection (line &a, line &b) { return ((ld)b.b - a.b) / ((ld)a.k - b.k); } void add_line (line last, int Id) { while (sz(r) >= 2 && intersection (r[sz(r) - 2], r[sz(r) - 1]) > intersection (r[sz(r)-2], last)) { r.pop_back(); id.pop_back(); } r.pb (last); id.pb (Id); } pair <ll, int> get2 (ll x, vec<line> &a) { int l = 0, r = sz(a)-2, ans = sz(a)-1; while (l <= r) { int mid = (l+r) >> 1; if (intersection (a[mid], a[mid + 1]) >= x) r = mid-1, ans = mid; else l = mid+1; } return {a[ans].get(x), id[ans]}; } pair <ll, int> get (ll x) { ptr = min (ptr, sz(r) - 1); while (ptr + 1 < sz(r) && intersection (r[ptr], r[ptr + 1]) < x) ptr++; return get2 (x, r); return {r[ptr].get (x), id[ptr]}; } void show() { cout << endl; for (int i = 0; i < sz(r); i++) cout << r[i].k << ' ' << r[i].b << " "; cout << endl; cout << "X: "; for (int i = 0; i < sz(r) - 1; i++) cout << intersection (r[i], r[i + 1]) << ' '; cout << endl; } }; int main() { Read_rap(); //localInput(); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i]; ll dp[n + 2] = {0}, nw[n + 2] = {0}; CHT T; for (int i = 1; i <= k; i++) { T.clear(); for (int j = i + 1; j <= n; j++) { if (j > i + 1 && pref[j] == pref[j - 1]) { nw[j] = nw[j - 1]; pr[i][j] = pr[i][j - 1]; continue; } j--; T.add_line ( {pref[j], -pref[j] * pref[j] + dp[j]}, j); j++; tie (nw[j], pr[i][j]) = T.get (pref[j]); } //T.show(); for (int j = 1; j <= n; j++) dp[j] = nw[j]; } cout << dp[n] << endl; for (int i = k, j = n; i >= 1; ) { j = pr[i][j]; i--; assert (j); cout << j << ' '; } return 0; } // Coded by Z..

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

sequence.cpp: In function 'void files(std::__cxx11::string)':
sequence.cpp:37:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".in").c_str(),"r",stdin);
                                                  ^
sequence.cpp:38:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".out").c_str(),"w",stdout);
                                                    ^
sequence.cpp: In function 'void localInput(std::__cxx11::string)':
sequence.cpp:43:37: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen (in.c_str(), "r", stdin);
                                     ^
#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...