oj.uz

Submission #986550

# Submission time Handle Problem Language Result Execution time Memory
986550 2024-05-20T18:10:42 Z idiotcomputer Building Bridges (CEOI17_building) C++11
60 / 100
 57 ms 5712 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 = 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 << 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 49 ms 2140 KB Output is correct
2 Correct 48 ms 2056 KB Output is correct
3 Correct 46 ms 1884 KB Output is correct
4 Correct 42 ms 2036 KB Output is correct
5 Correct 51 ms 3408 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 49 ms 2140 KB Output is correct
7 Correct 48 ms 2056 KB Output is correct
8 Correct 46 ms 1884 KB Output is correct
9 Correct 42 ms 2036 KB Output is correct
10 Correct 51 ms 3408 KB Output is correct
11 Correct 39 ms 2044 KB Output is correct
12 Correct 45 ms 1884 KB Output is correct
13 Correct 29 ms 1884 KB Output is correct
14 Correct 44 ms 1884 KB Output is correct
15 Incorrect 57 ms 5712 KB Output isn't correct
16 Halted 0 ms 0 KB -