oj.uz

Submission #986548

# Submission time Handle Problem Language Result Execution time Memory
986548 2024-05-20T18:10:20 Z idiotcomputer Building Bridges (CEOI17_building) C++11
60 / 100
 65 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);
    }
    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 0 ms 348 KB Output is correct
2 Correct 0 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 51 ms 2092 KB Output is correct
2 Correct 55 ms 2140 KB Output is correct
3 Correct 51 ms 1884 KB Output is correct
4 Correct 56 ms 2044 KB Output is correct
5 Correct 57 ms 3408 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 51 ms 2092 KB Output is correct
7 Correct 55 ms 2140 KB Output is correct
8 Correct 51 ms 1884 KB Output is correct
9 Correct 56 ms 2044 KB Output is correct
10 Correct 57 ms 3408 KB Output is correct
11 Correct 43 ms 1884 KB Output is correct
12 Correct 53 ms 1884 KB Output is correct
13 Correct 31 ms 1880 KB Output is correct
14 Correct 49 ms 2136 KB Output is correct
15 Incorrect 65 ms 5712 KB Output isn't correct
16 Halted 0 ms 0 KB -