oj.uz

Submission #54967

# Submission time Handle Problem Language Result Execution time Memory
54967 2018-07-05T15:12:50 Z istlemin Building Bridges (CEOI17_building) C++14
30 / 100
 1040 ms 5000 KB 
#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);
                rep(z,0,3){
					if(it==toLeft[j].begin()) break;
                    --it;
                }
                rep(z,0,5){
					if(it==toLeft[j].end()) break;
                    best = min(best,(h[0]-*it)*(h[0]-*it) + (h[i]-*it)*(h[i]-*it) - (j-20) - w[i]);
                    ++it;
                }
            }

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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 4 ms 576 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1040 ms 5000 KB Output is correct
2 Correct 863 ms 5000 KB Output is correct
3 Correct 909 ms 5000 KB Output is correct
4 Incorrect 106 ms 5000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 4 ms 576 KB Output is correct
6 Correct 1040 ms 5000 KB Output is correct
7 Correct 863 ms 5000 KB Output is correct
8 Correct 909 ms 5000 KB Output is correct
9 Incorrect 106 ms 5000 KB Output isn't correct
10 Halted 0 ms 0 KB -