제출 #564311

#제출 시각아이디문제언어결과실행 시간메모리
564311arayi수열 (APIO14_sequence)C++17
0 / 100
6 ms1876 KiB
// Arayi #include <bits/stdc++.h> #define fr first #define sc second #define MP make_pair #define ad push_back #define PB push_back #define fastio \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define lli long long int #define y1 arayikhalatyan #define j1 jigglypuff #define ld long double #define itn int #define pir pair<int, int> #define all(x) (x).begin(), (x).end() #define str string #define enl endl #define en endl #define cd complex<long double> #define vcd vector<cd> #define vii vector<int> #define vlli vector<lli> using namespace std; lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); } ld dist(ld x, ld y1, ld x2, ld y2) { return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2)); } lli S(lli a) { return (a * (a + 1LL)) / 2; } mt19937 rnd(363542); char vow[] = {'a', 'e', 'i', 'o', 'u'}; int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0}; int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0}; char dc[] = {'R', 'D', 'L', 'U'}; const int N = 2e5 + 20; const lli mod = 1e9 + 7; const ld pi = acos(-1); const int T = 200; lli bp(lli a, lli b = mod - 2LL) { lli ret = 1; while (b) { if (b & 1) ret *= a, ret %= mod; a *= a; a %= mod; b >>= 1; } return ret; } ostream &operator<<(ostream &c, pir a) { c << a.fr << " " << a.sc; return c; } template <class T> void maxi(T &a, T b) { a = max(a, b); } template <class T> void mini(T &a, T b) { a = min(a, b); } int n, k; lli dp[N][220]; lli a[N], pr[N]; ld f(int i, int i1, int x) { ld x1; ld a = pr[i1] - pr[i]; if (a != 0) x1 = ((ld)(dp[i1][x] - dp[i][x])) / a; else if (dp[i1][x] > dp[i][x]) x1 = 1e10; else x1 = -1; return x1; } int main() { fastio; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> a[i]; pr[i] = a[i]; if (i) pr[i] += pr[i - 1]; } /*for (int i = 0; i < n; i++) dp[i][1] = pr[i] * (pr[n - 1] - pr[i]); //, cout << dp[i][1] << " "; // cout << endl; int ii = 0; if (k == 1) { for (int i = 0; i < n; i++) if (dp[i][1] > dp[ii][1]) ii = i; cout << dp[ii][1] << endl; cout << ii + 1 << endl; return 0; } for (int x = 2; x <= k; x++) { vector<pair<ld, int>> fp; fp.ad(MP(1e10, 0)); for (int i = 1; i < n; i++) { while ((int)fp.size() > 1 && f(fp.back().sc, i, x - 1) > fp.back().fr) fp.pop_back(); fp.ad(MP(f(fp.back().sc, i, x - 1), i)); } int i1 = 0; for (int i = 0; i < n - 1; i++) { dp[i][x] = pr[i] * (pr[n - 1] - pr[i]); ld x1 = pr[n - 1] - pr[i]; while (i1 + 1 < (int)fp.size() && x1 <= fp[i1 + 1].fr) i1++; // cout << fp[i1].sc << "-"; dp[i][x] += dp[fp[i1].sc][x - 1]; dp[i][x] -= pr[fp[i1].sc] * x1; // cout << dp[i][x] << " "; if (x == k && dp[i][x] > dp[ii][x]) ii = i; } } cout << dp[ii][k] << endl; vii fp; fp.ad(ii); for (int i = k - 1; i > 0; i--) { for (int j = ii - 1; j >= 0; j--) { if (dp[j][i] + (pr[n - 1] - pr[ii]) * (pr[ii] - pr[j]) == dp[ii][i + 1]) { fp.ad(j); ii = j; break; } } } reverse(all(fp)); for (auto p : fp) cout << p + 1 << " "; cout << endl;*/ return 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...