제출 #408963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408963		Pichon5	Building Bridges (CEOI17_building)	C++17	30 / 100	72 ms	10156 KiB

building

#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
 
//"\n"
//__builtin_popcount
using namespace std;
const int tam=1005;
int n;
ll dp[tam][tam];
vi h,w;
ll f(int pos, int ant){
    if(pos==n-1)return (h[pos]-h[ant])*(h[pos]-h[ant]);
    if(dp[pos][ant]!=-1)return dp[pos][ant];
    dp[pos][ant]=w[pos]+f(pos+1,ant);
    dp[pos][ant]=min(dp[pos][ant],(h[pos]-h[ant])*(h[pos]-h[ant])+f(pos+1,pos));
    return dp[pos][ant];
}
int main()
{
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        h.pb(x);
    }
    for(int i=0;i<n;i++){
        cin>>x;
        w.pb(x);
    }
    memset(dp,-1,sizeof(dp));
    cout<<f(1,0)<<endl;   
}

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40