oj.uz

Submission #61828

# Submission time Handle Problem Language Result Execution time Memory
61828 2018-07-26T18:41:04 Z IvanC Building Bridges (CEOI17_building) C++17
100 / 100
 682 ms 16208 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int MAXN = 1e5 + 10;
const int BUCKET = 320;
const ll INF = 1e18;
 
struct line{
	ll a,b;
	
	line(ll _a = 0,ll _b = 0){
		a = _a;
		b = _b;
	}
 
	ll get(ll x){return a*x + b;}
	ld get_ld(ld x){return a*x + b;}
 
	bool operator<(const line& other)const{
		if(a != other.a) return a > other.a;
		return b > other.b;
	}
 
};
 
vector<line> hull,light_lines;
ll dp[MAXN],H[MAXN],W[MAXN],pref[MAXN],b[MAXN],a[MAXN];
int N;
 
ld inter(line l1,line l2){
	return -1.0*ld(l1.b - l2.b)/ld(l1.a - l2.a);
}
 
bool useless(line l1,line l2,line l3){
	ld x = inter(l1,l3);
	return l2.get_ld(x) > l3.get_ld(x);
}
 
void add_line(line l){
 
	while(!hull.empty() && hull.back().a == l.a){
		hull.pop_back();
	}
	while(hull.size() >= 2 && useless(hull[hull.size()-2],hull.back(),l)){
		hull.pop_back();
	}
	hull.push_back(l);
 
}
 
void rebuild(){
 
	vector<line> temp;
	sort(light_lines.begin(),light_lines.end());
	merge(hull.begin(),hull.end(),light_lines.begin(),light_lines.end(),back_inserter(temp));
	hull.clear();
	light_lines.clear();
	for(line l : temp){
		add_line(l);
	}
 
}
 
void add(ll a,ll b){
	line l(a,b);
	light_lines.push_back(l);
	if(light_lines.size() >= BUCKET) rebuild();
}
 
ll query(ll x){
	ll ans = INF;
	for(line l : light_lines) ans = min(ans, l.get(x) );
	if(hull.empty()) return ans;
	ans = min(ans, hull.back().get(x) );
	int ini = 0,fim = hull.size() - 2,meio;
	while(ini <= fim){
		meio = ini + (fim - ini)/2;
		ll f1 = hull[meio].get(x),f2 = hull[meio+1].get(x);
		ans = min(ans, min(f1,f2) );
		if(f1 < f2){
			fim = meio - 1;
		}
		else{
			ini = meio + 1;
		}
	}
	return min(ans,hull[meio].get(x));
}
 
int main(){
 
	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%lld",&H[i]);
	}
	for(int i = 1;i<=N;i++){
		scanf("%lld",&W[i]);
		pref[i] = W[i] + pref[i-1];
	}
 
	dp[1] = 0;
	a[1] = -2*H[1];
	b[1] = -pref[1] + dp[1] + H[1]*H[1];
	add(a[1],b[1]);
 
	for(int i = 2;i<=N;i++){
		dp[i] = query(H[i]) + H[i]*H[i] + pref[i-1];
		a[i] = -2*H[i];
		b[i] = -pref[i] + dp[i] + H[i]*H[i];
		add(a[i],b[i]);
	}
 
	cout << dp[N] << endl;
 
	return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
building.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&H[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&W[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp: In function 'll query(ll)':
building.cpp:78:36: warning: 'meio' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int ini = 0,fim = hull.size() - 2,meio;
                                    ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 544 KB Output is correct
5 Correct 4 ms 592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5320 KB Output is correct
2 Correct 81 ms 5320 KB Output is correct
3 Correct 86 ms 5384 KB Output is correct
4 Correct 84 ms 5384 KB Output is correct
5 Correct 154 ms 6460 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 544 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 132 ms 5320 KB Output is correct
7 Correct 81 ms 5320 KB Output is correct
8 Correct 86 ms 5384 KB Output is correct
9 Correct 84 ms 5384 KB Output is correct
10 Correct 154 ms 6460 KB Output is correct
11 Correct 111 ms 6548 KB Output is correct
12 Correct 86 ms 7540 KB Output is correct
13 Correct 95 ms 8692 KB Output is correct
14 Correct 94 ms 9992 KB Output is correct
15 Correct 682 ms 16208 KB Output is correct
16 Correct 160 ms 16208 KB Output is correct
17 Correct 61 ms 16208 KB Output is correct
18 Correct 52 ms 16208 KB Output is correct