oj.uz

답안 #778028

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
778028 2023-07-10T03:27:30 Z horiiseun 수열 (APIO14_sequence) C++17
100 / 100
 684 ms 90204 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <random>
#include <string>
#include <bitset>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
    #define D(...)
#endif
 
const double EPS = numeric_limits<double>::epsilon();
 
struct Line {
    ll m;
    ll c;
    double p; 
    int ct;
};
 
struct CHT {
    vector<Line> lines;
    int k;
 
    double getX(ll m1, ll c1, ll m2, ll c2) {
        return (double) (c1 - c2) / (double) (m2 - m1 + EPS);
    }
 
    void addLine(ll m, ll c, int ct) {
        double p = LLONG_MIN;
        while (!lines.empty()) {
            p = getX(m, c, lines.back().m, lines.back().c);
            if (p < lines.back().p - EPS) lines.pop_back();
            else break;
        }
        lines.push_back({m, c, p, ct});
    }
 
    pair<ll, int> getY(ll x) {
        int l = 0, r = lines.size() - 1, ret = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            if (lines[m].p <= x + EPS) {
                ret = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return {lines[ret].m * x + lines[ret].c, lines[ret].ct};
    }
 
    pair<ll, int> getYFast(ll x) {
        k = min(k, (int) lines.size() - 1);
        while (k + 1 < lines.size() && lines[k + 1].p <= x + EPS) {
            k++;
        }
        return {lines[k].m * x + lines[k].c, lines[k].ct};
    }
 
    CHT() {}
 
    void init() {
        lines.clear();
        k = 0;
    }
};
 
int n, k, a[100005], from[100005][205], idx;
ll dp[100005][2], pref[100005], mx;
vector<int> path;
CHT *chc, *chp;
 
void prnt(int pos, int ct) {
    if (ct == 1) return;
    prnt(from[pos][ct], ct - 1);
    cout << from[pos][ct] << " ";
}
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = a[i];
        pref[i] += pref[i - 1];
    }
 
    if (n <= 1000) {
        for (int i = 1; i <= n; i++) {
            dp[i][1] = pref[i] * (pref[n] - pref[i]);
        }
        for (int i = 2; i <= k + 1; i++) {
            for (int j = i; j <= n; j++) {
                for (int m = 1; m < j; m++) {
                    if (dp[j][i % 2] <= dp[m][(i + 1) % 2] + (pref[j] - pref[m]) * (pref[n] - pref[j])) {
                        dp[j][i % 2] = dp[m][(i + 1) % 2] + (pref[j] - pref[m]) * (pref[n] - pref[j]);
                        from[j][i] = m;
                    }
                }
            }
        }
        cout << dp[n][(k + 1) % 2] << "\n";
    } else {
        chc = new CHT(), chp = new CHT();
        for (int i = 1; i <= n; i++) {
            dp[i][1] = pref[i] * (pref[n] - pref[i]);
            chp->addLine(pref[i], dp[i][1] - pref[i] * pref[n], i);
        }
        for (int i = 2; i <= k + 1; i++) {
            for (int j = i; j <= n; j++) {
                pair<ll, int> curr = chp->getYFast(pref[j]);
                dp[j][i % 2] = curr.f + (pref[n] - pref[j]) * pref[j];
                from[j][i] = curr.s;
                chc->addLine(pref[j], dp[j][i % 2] - pref[j] * pref[n], j);
            }
            chp->init();
            swap(chp, chc);
        }
        cout << dp[n][(k + 1) % 2] << "\n"; 
    }
    prnt(n, k + 1);
 
}

Compilation message

sequence.cpp: In member function 'std::pair<long long int, int> CHT::getYFast(long long int)':
sequence.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while (k + 1 < lines.size() && lines[k + 1].p <= x + EPS) {
      |                ~~~~~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 340 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 340 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 340 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 340 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 340 KB contestant found the optimal answer: 1 == 1
7 Correct 1 ms 340 KB contestant found the optimal answer: 1 == 1
8 Correct 1 ms 340 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 324 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 340 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 328 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 340 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 340 KB contestant found the optimal answer: 140072 == 140072
14 Correct 1 ms 340 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 1 ms 340 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 320 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 328 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 328 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 1 ms 340 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 340 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 340 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 1 ms 340 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 340 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 340 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 340 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 328 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 468 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 3 ms 468 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 468 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 3 ms 452 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 4 ms 516 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 4 ms 516 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 2 ms 468 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 1 ms 468 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 2 ms 448 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1092 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 2 ms 1108 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 96 ms 1172 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 3 ms 1108 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 98 ms 1152 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 83 ms 1100 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 104 ms 1224 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 95 ms 1160 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 22 ms 1172 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 40 ms 1108 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9300 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 5 ms 9172 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 41 ms 9428 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 5 ms 9432 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 35 ms 9172 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 38 ms 9244 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 34 ms 9432 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 29 ms 9432 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 34 ms 9372 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 42 ms 9304 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 88564 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 54 ms 88708 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 504 ms 90204 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 49 ms 90188 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 684 ms 88628 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 463 ms 90084 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 425 ms 90108 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 354 ms 89944 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 413 ms 89428 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 527 ms 89428 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845