oj.uz

Submission #54970

# Submission time Handle Problem Language Result Execution time Memory
54970 2018-07-05T15:17:09 Z istlemin Building Bridges (CEOI17_building) C++14
60 / 100
 1055 ms 7756 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) + (h[n-1]-h[i])*(h[n-1]-h[i]) - (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 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 5 ms 540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 4928 KB Output is correct
2 Correct 864 ms 4996 KB Output is correct
3 Correct 1055 ms 5044 KB Output is correct
4 Correct 156 ms 5044 KB Output is correct
5 Correct 682 ms 7756 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 3 ms 448 KB Output is correct
5 Correct 5 ms 540 KB Output is correct
6 Correct 963 ms 4928 KB Output is correct
7 Correct 864 ms 4996 KB Output is correct
8 Correct 1055 ms 5044 KB Output is correct
9 Correct 156 ms 5044 KB Output is correct
10 Correct 682 ms 7756 KB Output is correct
11 Runtime error 49 ms 7756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -