Submission #537907

#	Time	Username	Problem	Language	Result	Execution time	Memory
537907		Lobo	구슬과 끈 (APIO14_beads)	C++17	0 / 100	1 ms	340 KiB

beads

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 110000

int n, k, a[maxn], ps[maxn], dp[maxn][2];
set<pair<pair<int,int>,pair<int,int>>> cht, chtlr;
//cht -> a,b,l,r
//chtlr -> l,r,a,b

int f(int a, int b, int x) {
    return a*x + b;
}

dbl interx(int a1, int b1, int a2, int b2) {
    return (dbl) (b2-b1)/(a1-a2);
}

void resetcht() {
    cht.clear();
    chtlr.clear();

    cht.insert(mp(mp(0,0),mp(-inf1,+inf1)));
    chtlr.insert(mp(mp(-inf1,+inf1),mp(0,0)));
}

void attcht(int a, int b) {
    //f(x) = a*x + b

    //pega qual o lugar que eu seria colocado no set
    auto it = cht.upper_bound(mp(mp(a,b),mp(0,0)));
    //left = (beg,it-1)
    //right = (it,end-1)

    vector<pair<pair<int,int>,pair<int,int>>> rem, add;

    int ansr = -inf1;
    int ansl = +inf1;
    //primeiro tiro tudo da esquerda
    auto itl = it;
    while(itl != cht.begin()) {
        itl--; //ve se consegue tirar it1

        int al = itl->fr.fr;
        int bl = itl->fr.sc;
        int l = itl->sc.fr;
        int r = itl->sc.sc;


        //se em l o novo for melhor que o antigo, entao apaga o antigo
        if(f(a,b,l) >= f(al,bl,l)) {
            ansl = l;
            ansr = max(ansr,r);
            rem.pb(mp(mp(al,bl),mp(l,r)));
        }
        else if(f(a,b,r) >= f(al,bl,r)) {
            //find the intersect (a,b) and (al,bl)
            //a != al
            //f(a,b) >= f(al,bl) in ceil(x)
            int x = ceil(interx(a,b,al,bl));
            rem.pb(mp(mp(al,bl),mp(l,r)));
            add.pb(mp(mp(al,bl),mp(l,x-1)));
            ansr = max(ansr,r);
            ansl = x;
            break;
        }
        else {
            break;
        }
    }

    auto itr = it;
    while(itr != cht.end()) {
        //ve se consegue tirar itr

        int ar = itr->fr.fr;
        int br = itr->fr.sc;
        int l = itr->sc.fr;
        int r = itr->sc.sc;

        //se em r o novo for melhor que o antigo, entao apaga o antigo
        if(f(a,b,r) >= f(ar,br,r)) {
            ansr = r;
            ansl = min(ansl,l);
            rem.pb(mp(mp(ar,br),mp(l,r)));
        }
        else if(f(a,b,l) >= f(ar,br,l)) {
            //find the intersect (a,b) and (ar,br)
            //a != ar
            //f(a,b) >= f(ar,br) at floor(x)
            int x = floor(interx(a,b,ar,br));
            rem.pb(mp(mp(ar,br),mp(l,r)));
            add.pb(mp(mp(ar,br),mp(x+1,r)));
            ansr = x;
            ansl = min(ansl,l);
            break;
        }
        else {
            break;
        }
        itr++;
    }

    for(auto x : rem) {
        cht.erase(x);
        chtlr.erase(mp(x.sc,x.fr));
    }

    for(auto x : add) {
        cht.insert(x);
        chtlr.insert(mp(x.sc,x.fr));
    }

    if(ansl <= ansr) {
        cht.insert(mp(mp(a,b),mp(ansl,ansr)));
        chtlr.insert(mp(mp(ansl,ansr),mp(a,b)));
    }
}

int qrr(int x) {
    auto it = chtlr.upper_bound(mp(mp(x,inf),mp(0,0)));
    it--;
    int a = it->sc.fr;
    int b = it->sc.sc;

    return f(a,b,x);
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        ps[i] = ps[i-1] + a[i];
    }

    for(int j = 0; j <= k; j++) {
        resetcht();
        //dp[0][j] = 0
        for(int i = 1; i <= n; i++) {
            auto qr = qrr(ps[i]);
            dp[i][j&1] = qrr(ps[i]);
            attcht(ps[i],dp[i][(j+1)&1]-ps[i]*ps[i]);
        }
    }

    cout << dp[n][k&1] << endl;
    cout << "1 3 5 " << endl;

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);

    int tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Compilation message (stderr)

beads.cpp: In function 'void solve()':
beads.cpp:151:18: warning: unused variable 'qr' [-Wunused-variable]
  151 |             auto qr = qrr(ps[i]);
      |                  ^~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43