Submission #54965

#	Time	Username	Problem	Language	Result	Execution time	Memory
54965		istlemin	Building Bridges (CEOI17_building)	C++14	30 / 100	740 ms	4956 KiB

building

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n;
vi h;
vi w;

int main(){
	cin.sync_with_stdio(false);
	cin>>n;
	h.resize(n);
	w.resize(n);

    rep(i,0,n)
        cin>>h[i];
    ll sumW = 0;
    rep(i,0,n){
        cin>>w[i];
        sumW += w[i];
	}
	if(n<=1000){
		vi dp(n,1e18);
		dp[0] = -w[0];
		rep(i,1,n){
			rep(j,0,i){
				dp[i] = min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j]));
			}
			dp[i] -= w[i];
			//cout<<dp[i]<<" ";
		}
		cout<<sumW + dp[n-1]<<endl;
	} else {
        ll best = (h[0]-h[n-1])*(h[0]-h[n-1]);

        rep(i,1,n-1){
			best = min(best,(h[0]-h[i])*(h[0]-h[i]) + (h[n-1]-h[i])*(h[n-1]-h[i]) - w[i]);
        }

        vector<set<ll> > toLeft(41);

        rep(i,1,n-1){
            ll target = (h[i]+h[0])/2;

            rep(j,0,41){
                auto it = toLeft[j].upper_bound(target);
                if(it!=toLeft[j].end()){
                    best = min(best,(h[0]-*it)*(h[0]-*it) + (h[i]-*it)*(h[i]-*it) - (j-20) - w[i]);
				}
                if(it!=toLeft[j].begin()){
					it--;
                    best = min(best,(h[0]-*it)*(h[0]-*it) + (h[i]-*it)*(h[i]-*it) - (j-20) - w[i]);
				}
            }

            toLeft[w[i]+20].insert(h[i]);
        }

        best += sumW - w[0] - w[n-1];
        cout<<best<<endl;
	}
}

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