Submission #644802

#	Time	Username	Problem	Language	Result	Execution time	Memory
644802		Richem	Building Bridges (CEOI17_building)	C++14	30 / 100	78 ms	36588 KiB

building

#include <iostream>
#define int long long
using namespace std;

const int MAX_PILLIER = 1e5+42, MAX_FEUILLE = (1 << 20), INF = 1e9;

struct Ligne{
    int coeff, add;

    int f(int x) {return coeff * x + add;}
};

int nbPillier;

int hauteur[MAX_PILLIER];
int somme[MAX_PILLIER] = {0};

void input() {
    cin >> nbPillier;

    for(int i = 0; i < nbPillier; i++)
        cin >> hauteur[i];

    for(int i = 1; i <= nbPillier; i++) {
        cin >> somme[i];

        somme[i] += somme[i-1];
    }
}

Ligne ligne[MAX_FEUILLE*2];

int getMin(int x) {
    int pos = x + MAX_FEUILLE;
    int rep = INF;

    for(; pos > 0; pos /= 2) 
        rep = min(rep, ligne[pos].f(x));

    return rep;
}

void ajoutLigne(Ligne nouv, int pos, int deb, int fin) {
    int milieu = (deb + fin) / 2;

    Ligne cur = ligne[pos];

    if(nouv.f(milieu) < cur.f(milieu)) 
        swap(cur, nouv);

    ligne[pos] = cur;

    if(deb == fin-1)
        return;

    if(nouv.f(deb) < cur.f(deb)) 
        ajoutLigne(nouv, pos*2, deb, milieu);
    else
        ajoutLigne(nouv, pos*2+1, milieu, fin);
}

int dp[MAX_PILLIER];

signed main() {
    input();

    for(int i = 1; i < MAX_FEUILLE*2; i++) ligne[i] = {INF, 0};
    
    ajoutLigne({-2 * hauteur[0], hauteur[0] * hauteur[0] - somme[1]}, 1, 0, MAX_FEUILLE);

    for(int cur = 1; cur < nbPillier; cur++) {
        dp[cur] = getMin(hauteur[cur]) + somme[cur] + hauteur[cur] * hauteur[cur];

        ajoutLigne({-2 * hauteur[cur], dp[cur] + hauteur[cur] * hauteur[cur] - somme[cur+1]}, 1, 0, MAX_FEUILLE);
    }
 
    cout << dp[nbPillier-1];
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40