oj.uz

Submission #241561

# Submission time Handle Problem Language Result Execution time Memory
241561 2020-06-24T13:00:00 Z kimbj0709 Building Bridges (CEOI17_building) C++14
0 / 100
 89 ms 10864 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<int> vect3;
struct line{
    int m,c;
    int operator()(int x){
        return m*x+c;
    }
}a[maxn*4];
void insert(int node,int start,int end,line l){
    if(start==end){
        if(a[node](vect3[start])<l(vect3[start])){
            a[node] = l;
        }
        return;
    }
    if(a[node].m>l.m){
        swap(a[node],l);
    }
    int mid = (start+end)/2;
    if(a[node](vect3[mid])<l(vect3[mid])){
        swap(a[node],l);
        insert(node*2+1,start,mid,l);
    }
    else{
        insert(node*2+2,mid+1,end,l);
    }
}
int query(int node,int start,int end,int pos){
    if(start==end){
        return a[node](vect3[pos]);
    }
    int mid = (start+end)/2;
    if(pos<=mid){
        return max(a[node](vect3[pos]),query(node*2+1,start,mid,pos));
    }
    else{
        return max(a[node](vect3[pos]),query(node*2+2,mid+1,end,pos));
    }
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_input;
    vector<int> vect1;
    vector<int> vect2;
    vector<int> dp(maxn);
    int input;
    cin >> no_of_input;
    for(int i=0;i<no_of_input;i++){
        cin >> input;
        vect1.push_back(input);
    }
    for(int i=0;i<no_of_input;i++){
        cin >> input;
        vect2.push_back(input);
    }
    vect3 = vect1;
    sort(vect3.begin(),vect3.end());
    for(int i=0;i<maxn*4;i++){
        a[i] = {0,-INT_MAX};
    }
    cout << "YES" << endl;
    insert(0,0,vect3.size()-1,{2*vect1[0],-vect1[0]*vect1[0]});
    for(int i=1;i<no_of_input;i++){
        int pos = lower_bound(vect3.begin(),vect3.end(),vect1[i])-vect3.begin();
        int mini = query(0,0,vect3.size()-1,pos);
        dp[i] = -mini+vect1[i]*vect1[i]-vect2[i];
        insert(0,0,vect3.size()-1,{2*vect1[i],-(dp[i]+vect1[i]*vect1[i])});
    }
    int sum = 0;
    for(auto k:vect2){
        sum += k;
    }
    cout << dp[no_of_input-1]+sum;

}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 10864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 7424 KB Output isn't correct
2 Halted 0 ms 0 KB -