oj.uz

Submission #47232

# Submission time Handle Problem Language Result Execution time Memory
47232 2018-04-29T10:48:59 Z robert Building Bridges (CEOI17_building) C++14
30 / 100
 82 ms 6776 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4356 KB Output is correct
3 Correct 5 ms 4428 KB Output is correct
4 Correct 15 ms 4476 KB Output is correct
5 Correct 15 ms 4476 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4216 KB Output is correct
2 Correct 5 ms 4356 KB Output is correct
3 Correct 5 ms 4428 KB Output is correct
4 Correct 15 ms 4476 KB Output is correct
5 Correct 15 ms 4476 KB Output is correct
6 Incorrect 82 ms 6776 KB Output isn't correct
7 Halted 0 ms 0 KB -