Submission #47232

#	Time	Username	Problem	Language	Result	Execution time	Memory
47232		robert	Building Bridges (CEOI17_building)	C++14	30 / 100	82 ms	6776 KiB

building

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int N;
int h[100100], w[100100];
int m[1001][1000];

int solve(int n, int ln){
	if(n==0){
		///first node
		return solve(n+1, n);
	}
	else if(n==N-1){
		//last node
		return abs(h[n]-h[ln])*abs(h[n]-h[ln]);
	}
	if(m[n][ln]!=-1)
		return m[n][ln];
	return m[n][ln] = min(solve(n+1, n)+(abs(h[n]-h[ln])*abs(h[n]-h[ln])), solve(n+1, ln)+w[n]);
}

int main(){
	cin>>N;
	memset(m, -1, sizeof(m));
	for(int n=0; n<N; n++){
		cin>>h[n];
	}
	for(int n=0; n<N; n++)
		cin>>w[n];
	vector<int> m(N+1, -1);
	priority_queue<pair<int, int> > q; q.push({0, N-1});
	for(int n=N-2; n>=1; n--){
		while(!q.empty()){
			pair<int, int> t = q.top(); q.pop();
			t.first = -t.first;
			 
		}
	}	
	cout << solve(0, 0) << endl;
	return 0;
}

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