Submission #241565

#	Time	Username	Problem	Language	Result	Execution time	Memory
241565		kimbj0709	Building Bridges (CEOI17_building)	C++14	100 / 100	105 ms	11128 KiB

building

#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,-LLONG_MAX};
    }
    insert(0,0,vect3.size()-1,{2*vect1[0],-(vect1[0]*vect1[0]-vect2[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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40