oj.uz

Submission #380568

# Submission time Handle Problem Language Result Execution time Memory
380568 2021-03-22T11:10:36 Z mariowong Building Bridges (CEOI17_building) C++14
100 / 100
 276 ms 8160 KB 
#include <bits/stdc++.h>
using namespace std;


struct cht{
	long long dpval,hgt,psum,indx;
}b;
vector <cht> v;
vector <pair<long long,long long>  > now;
long long n,dp[100005],h[100005],w[100005],ps[100005],a[100005],l,r;
long long lft,rht,midd,indx;
bool cmp(cht a1,cht a2){
	return ((a1.hgt < a2.hgt) || (a1.hgt == a2.hgt) && a1.dpval-a1.psum < a2.dpval-a2.psum);
}
long double m(int j,int k){
	if (h[j] == h[k])
	return 1e18;
	return (long double)((dp[j]-ps[j]+h[j]*h[j])-(dp[k]-ps[k]+h[k]*h[k]))/(long double)(2*(h[j]-h[k]));
}
void solve(int x,int y){
	if (x == y);
	else
	{
		int mid=(x+y)/2;
		solve(x,mid);
		l=1; r=1; v.clear(); now.clear();
		for (int i=x;i<=mid;i++){
			b.dpval=dp[i]; b.hgt=h[i]; b.psum=ps[i]; b.indx=i;
			v.push_back(b);
		}
		sort(v.begin(),v.end(),cmp);
		for (int i=0;i<v.size();i++){
			while (r-l >= 2 && m(a[r-2],a[r-1]) >= m(a[r-1],v[i].indx)) r--;
			a[r]=v[i].indx; r++; 
		}
		for (int i=mid+1;i<=y;i++){
			now.push_back(make_pair(h[i],i));
		}
		for (int i=0;i<now.size();i++){
			lft=l; rht=r-1;
			while (lft < rht){
				midd=(lft+rht)/2;
				if (m(a[midd],a[midd+1]) < now[i].first)
				lft=midd+1;
				else
				rht=midd;
			}
			indx=now[i].second;
		//	if (indx == 20303)
		//	cout << x << " " << y << " " << indx << " " << l << " " << r << " " << lft << " " <<  m(a[l],a[l+1]) << ">=" << now[i].first << " "  << a[l] << " " <<  dp[a[l]] << " " << ps[indx-1]-ps[a[l]] << " " << (h[indx]-h[a[l]]) <<"\n";
			dp[indx]=min(dp[indx],dp[a[lft]]+ps[indx-1]-ps[a[lft]]+(h[indx]-h[a[lft]])*(h[indx]-h[a[lft]]));
		}
		solve(mid+1,y);
	}
}
int main(){
	ios::sync_with_stdio(false);
//	freopen("test_input.txt","r",stdin);
	cin >> n;
	for (int i=1;i<=n;i++){
		cin >> h[i];
		if (i != 1)
		dp[i]=1e18;
	}
	for (int i=1;i<=n;i++){
		cin >> w[i];
		ps[i]=ps[i-1]+w[i]; 
	}
	solve(1,n);
	cout << dp[n] << "\n";
	return 0;
}

Compilation message

building.cpp: In function 'bool cmp(cht, cht)':
building.cpp:13:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |  return ((a1.hgt < a2.hgt) || (a1.hgt == a2.hgt) && a1.dpval-a1.psum < a2.dpval-a2.psum);
      |                               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp: In function 'void solve(int, int)':
building.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<cht>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int i=0;i<v.size();i++){
      |                ~^~~~~~~~~
building.cpp:39:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int i=0;i<now.size();i++){
      |                ~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 7392 KB Output is correct
2 Correct 255 ms 6880 KB Output is correct
3 Correct 276 ms 7008 KB Output is correct
4 Correct 263 ms 7776 KB Output is correct
5 Correct 173 ms 7904 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 258 ms 7392 KB Output is correct
7 Correct 255 ms 6880 KB Output is correct
8 Correct 276 ms 7008 KB Output is correct
9 Correct 263 ms 7776 KB Output is correct
10 Correct 173 ms 7904 KB Output is correct
11 Correct 273 ms 8104 KB Output is correct
12 Correct 260 ms 8048 KB Output is correct
13 Correct 195 ms 8032 KB Output is correct
14 Correct 257 ms 8160 KB Output is correct
15 Correct 157 ms 8160 KB Output is correct
16 Correct 167 ms 8020 KB Output is correct
17 Correct 97 ms 7904 KB Output is correct
18 Correct 96 ms 7904 KB Output is correct