oj.uz

Submission #644802

# Submission time Handle Problem Language Result Execution time Memory
644802 2022-09-25T09:27:01 Z Richem Building Bridges (CEOI17_building) C++14
30 / 100
 78 ms 36588 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33108 KB Output is correct
2 Correct 13 ms 33072 KB Output is correct
3 Correct 13 ms 33108 KB Output is correct
4 Correct 13 ms 33104 KB Output is correct
5 Correct 13 ms 33132 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 36588 KB Output is correct
2 Correct 76 ms 36428 KB Output is correct
3 Correct 73 ms 36484 KB Output is correct
4 Correct 69 ms 36392 KB Output is correct
5 Incorrect 70 ms 36380 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33108 KB Output is correct
2 Correct 13 ms 33072 KB Output is correct
3 Correct 13 ms 33108 KB Output is correct
4 Correct 13 ms 33104 KB Output is correct
5 Correct 13 ms 33132 KB Output is correct
6 Correct 78 ms 36588 KB Output is correct
7 Correct 76 ms 36428 KB Output is correct
8 Correct 73 ms 36484 KB Output is correct
9 Correct 69 ms 36392 KB Output is correct
10 Incorrect 70 ms 36380 KB Output isn't correct
11 Halted 0 ms 0 KB -