oj.uz

답안 #1031364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031364 2024-07-22T18:35:55 Z Aiperiii Building Bridges (CEOI17_building) C++14
100 / 100
 102 ms 36788 KB 
#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e6+5;
pair <int,int> t[N*4];
void build(int v,int tl,int tr){
    t[v]={1e9,1e18};
    if(tl!=tr){
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
}
int f(int m,int x,int c){
    return m*x+c;
}
int get(int v,int tl,int tr,int x){
    if(tl==tr)return f(t[v].ff,x,t[v].ss);
    else{
        int tm=(tl+tr)/2;
        if(x<=tm)return min(f(t[v].ff,x,t[v].ss),get(v*2,tl,tm,x));
        else return min(f(t[v].ff,x,t[v].ss),get(v*2+1,tm+1,tr,x));
    }
}

void insert(int v,int tl,int tr,int m,int c){
    if(tl==tr){
        if(f(t[v].ff,tl,t[v].ss)>=f(m,tl,c)){
            t[v]={m,c};
        }
    }
    else{
        int tm=(tl+tr)/2;
        if(t[v].ff>m){
            swap(m,t[v].ff);
            swap(c,t[v].ss);
        }
        if(f(t[v].ff,tm,t[v].ss)<=f(m,tm,c)){
            insert(v*2,tl,tm,m,c);
        }
        else{
            insert(v*2+1,tm+1,tr,t[v].ff,t[v].ss);
            t[v]={m,c};
        }
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector <int> h(n+1),w(n+1),dp(n+1);
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=n;i++){
        cin>>w[i];
        sum+=w[i];
    }
    build(1,1,1e6);
    insert(1,1,1e6,-2*h[1],h[1]*h[1]-w[1]);
    for(int i=2;i<=n;i++){
        dp[i]=get(1,1,1e6,h[i])+h[i]*h[i]-w[i];
        //cout<<dp[i]<<" ";
        insert(1,1,1e6,-2*h[i],dp[i]+h[i]*h[i]);
    }
    cout<<dp[n]+sum<<"\n";
}
/*
 6
 3 8 7 1 6 6
 0 -1 9 1 2 0
 */

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33112 KB Output is correct
2 Correct 14 ms 33208 KB Output is correct
3 Correct 13 ms 33112 KB Output is correct
4 Correct 15 ms 33116 KB Output is correct
5 Correct 17 ms 33116 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 35408 KB Output is correct
2 Correct 60 ms 35412 KB Output is correct
3 Correct 60 ms 35564 KB Output is correct
4 Correct 59 ms 35412 KB Output is correct
5 Correct 64 ms 36448 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33112 KB Output is correct
2 Correct 14 ms 33208 KB Output is correct
3 Correct 13 ms 33112 KB Output is correct
4 Correct 15 ms 33116 KB Output is correct
5 Correct 17 ms 33116 KB Output is correct
6 Correct 62 ms 35408 KB Output is correct
7 Correct 60 ms 35412 KB Output is correct
8 Correct 60 ms 35564 KB Output is correct
9 Correct 59 ms 35412 KB Output is correct
10 Correct 64 ms 36448 KB Output is correct
11 Correct 102 ms 36688 KB Output is correct
12 Correct 74 ms 36576 KB Output is correct
13 Correct 98 ms 36576 KB Output is correct
14 Correct 79 ms 36788 KB Output is correct
15 Correct 55 ms 36320 KB Output is correct
16 Correct 55 ms 36324 KB Output is correct
17 Correct 58 ms 36704 KB Output is correct
18 Correct 56 ms 36688 KB Output is correct