oj.uz

Submission #241563

# Submission time Handle Problem Language Result Execution time Memory
241563 2020-06-24T13:02:31 Z kimbj0709 Building Bridges (CEOI17_building) C++14
30 / 100
 94 ms 10872 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};
    }
    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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9852 KB Output is correct
2 Correct 84 ms 10864 KB Output is correct
3 Correct 87 ms 10864 KB Output is correct
4 Correct 94 ms 10736 KB Output is correct
5 Incorrect 55 ms 10872 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 9 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 87 ms 9852 KB Output is correct
7 Correct 84 ms 10864 KB Output is correct
8 Correct 87 ms 10864 KB Output is correct
9 Correct 94 ms 10736 KB Output is correct
10 Incorrect 55 ms 10872 KB Output isn't correct