제출 #1178572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178572		peteza	수열 (APIO14_sequence)	C++20	100 / 100	967 ms	84040 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll neginf = -1e18;

struct Line {
    ll m, c;
    int cutidx = 0;
    ll operator()(ll x) {return m*x+c;}
    Line(ll _m, ll _c): m(_m), c(_c) {}
};

ll floordiv(ll a, ll b) {
    return a/b - ((a^b) < 0 && a%b);
}

bool bruh(Line old1, Line old2, Line toins) {
    //check if u should del or not
    if(toins.m == old2.m) return toins.c >= old2.c;
    return floordiv(toins.c - old1.c, old1.m - toins.m) < floordiv(old1.c - old2.c, old2.m - old1.m);
}

int n, k;
ll qs[200005];
ll dp[200005][2];
int par[200005][205];

void rec(int x, int k) {
    if(x == 0) return ;
    rec(par[x][k], k-1);
    if(par[x][k]) cout << par[x][k] << ' ';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++) {
        cin >> qs[i];
        qs[i] += qs[i-1];
    }
    for(int ck=2;ck<=k+1;ck++) {
        for(int i=0;i<=n;i++) dp[i][ck&1] = neginf;
        deque<Line> deq;
        for(int ci=ck-1;ci<n;ci++) {
            Line toins(qs[ci], dp[ci][(ck&1)^1] - qs[ci]*qs[ci]); toins.cutidx = ci;
            while(deq.size() > 1 && bruh(deq[deq.size()-2], deq.back(), toins)) deq.pop_back();
            //if(ck == k+1 && toins.cutidx == 7) cout << toins.m << " and " << deq.back().m << '\n';
            if(deq.empty() || toins.m != deq.back().m) deq.emplace_back(toins);
            /*if(ck == k+1 && toins.cutidx == 7) {
                for(auto &e:deq) cout << e.m << "x + " << e.c << " -> " << e.cutidx << '\n';
            }*/
            while(deq.size() > 1 && deq[0](qs[ci+1]) <= deq[1](qs[ci+1])) {
                //cout << "popping out " << deq[0].cutidx << '\n';
                deq.pop_front();
            }
            //cout << "using" << deq[0].cutidx << '\n';
            dp[ci+1][ck&1] = deq[0](qs[ci+1]);
            par[ci+1][ck] = deq[0].cutidx;
        }
        //cout << '\n';
    }
    cout << dp[n][(k&1)^1] << '\n';
    rec(n, k+1);

}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29