oj.uz

Submission #986537

# Submission time Handle Problem Language Result Execution time Memory
986537 2024-05-20T17:59:46 Z idiotcomputer Building Bridges (CEOI17_building) C++11
60 / 100
 61 ms 6740 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
 
//c + (hi - x)^2
// c + hi^2 + x^2 - 2hix
//lowest
struct line {
    ll m,c,x;
    bool t;
};
 
bool operator<(line a, line b){
    if (a.t || b.t) return a.x < b.x;
    if (a.m == b.m) return a.c > b.c;
    return a.m > b.m;
}
 
double isect(line a, line b){
    if (a.m == b.m) return INT_MIN;
    return ((double) (b.c-a.c) / (double) (a.m-b.m));
}
 
set<line> all;
 
void add(line a){
    auto it = all.lower_bound(a);
    if (it != all.end() && it != all.begin()){
        auto it2 = it;
        it2--;
        if (isect(*it2,a) >= isect(a,*it)) return;
    }
    //remove left 
    while (it != all.begin()){
        auto it2 = it;
        it2--;
        if (it2 == all.begin()) break;
        auto it3 = it2;
        it3--;
        if (isect(*it3,*it2) >= isect(*it2,a)) all.erase(it2);
        else break;
    }        
    //remove right
    while (it != all.end()){
        auto it2 = it;
        it2++;
        if (it2 == all.end()) break;
        if (isect(a,*it) >= isect(*it,*it2)){
            all.erase(it);
            it = it2;
        } else {
            break;
        }
    }
    if (it != all.begin()){
        line an = *prev(it);
        an.x = isect(*prev(it),a);
        all.erase(prev(it));
        all.insert(an);
        it = all.lower_bound(a);
    }
    if (it != all.end()) a.x = isect(a,*it);
    all.insert(a);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    ll h[n];
    ll w[n];
    for (int i =0; i < n; i++) cin >> h[i];
    for (int i =0; i < n; i++) cin >> w[i];
    
    ll csum = 0;
    for (int i =0; i < n; i++) csum += w[i];
    line temp;
    temp.m = -2*h[0];
    temp.c = h[0]*h[0]-w[0];
    temp.x = INT_MAX;
    temp.t = false;
    all.insert(temp);
    for (int i = 1; i < n; i++){
        temp.t = true;
        temp.x = h[i];
        auto it = all.lower_bound(temp);
        temp.c = 2*h[i]*h[i] + ((*it).m * h[i] + (*it).c) - w[i];
        if (i == n-1) cout << csum + temp.c - h[i]*h[i] << '\n';
        temp.m = -2*h[i];
        temp.t = false;
        add(temp);
        
    }
    
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3092 KB Output is correct
2 Correct 53 ms 2908 KB Output is correct
3 Correct 51 ms 3100 KB Output is correct
4 Correct 48 ms 2908 KB Output is correct
5 Correct 59 ms 4432 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 51 ms 3092 KB Output is correct
7 Correct 53 ms 2908 KB Output is correct
8 Correct 51 ms 3100 KB Output is correct
9 Correct 48 ms 2908 KB Output is correct
10 Correct 59 ms 4432 KB Output is correct
11 Correct 44 ms 3156 KB Output is correct
12 Correct 51 ms 3064 KB Output is correct
13 Correct 30 ms 2908 KB Output is correct
14 Correct 49 ms 3164 KB Output is correct
15 Incorrect 61 ms 6740 KB Output isn't correct
16 Halted 0 ms 0 KB -