oj.uz

Submission #986564

# Submission time Handle Problem Language Result Execution time Memory
986564 2024-05-20T18:24:04 Z idiotcomputer Building Bridges (CEOI17_building) C++11
100 / 100
 61 ms 9820 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];
    //cout << csum << '\n';
    line temp;
    temp.m = -2*h[0];
    temp.c = csum + h[0]*h[0]-w[0];
    temp.x = INT_MAX;
    temp.t = false;
    all.insert(temp);
   // cout << temp.c - h[0]*h[0]<< "\n";
    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 << temp.c - h[i]*h[i] << '\n';
        temp.x = INT_MAX;
        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 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 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 45 ms 2068 KB Output is correct
2 Correct 47 ms 1880 KB Output is correct
3 Correct 45 ms 2060 KB Output is correct
4 Correct 43 ms 1884 KB Output is correct
5 Correct 50 ms 3420 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 45 ms 2068 KB Output is correct
7 Correct 47 ms 1880 KB Output is correct
8 Correct 45 ms 2060 KB Output is correct
9 Correct 43 ms 1884 KB Output is correct
10 Correct 50 ms 3420 KB Output is correct
11 Correct 40 ms 1884 KB Output is correct
12 Correct 46 ms 1884 KB Output is correct
13 Correct 30 ms 1884 KB Output is correct
14 Correct 44 ms 1884 KB Output is correct
15 Correct 61 ms 9820 KB Output is correct
16 Correct 54 ms 4440 KB Output is correct
17 Correct 15 ms 2908 KB Output is correct
18 Correct 19 ms 2908 KB Output is correct