Submission #397425

#	Time	Username	Problem	Language	Result	Execution time	Memory
397425		Nicholas_Patrick	Building Bridges (CEOI17_building)	C++17	100 / 100	104 ms	6308 KiB

building

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct cht{
	struct line{
		long long m, c;
		line(long long m=0, long long c=1e18):m(m), c(c){}
		long long eval(long long x){
			return m*x+c;
		}
	};
	int n;
	vector<long long> x;
	vector<line> ch;
	cht(vector<int> init){
		sort(init.begin(), init.end());
		x.resize(n=unique(init.begin(), init.end())-init.begin());
		for(int i=n; i--;)
			x[i]=init[i];
		ch.resize(n*2-1);
	}
	void update(line y, int node, int curl, int curr){
		bool leftBetter=y.eval(x[curl])<=ch[node].eval(x[curl]),
			rightBetter=y.eval(x[curr-1])<=ch[node].eval(x[curr-1]);
		if(not leftBetter and not rightBetter)
			return;
		if(leftBetter and rightBetter){
			ch[node]=y;
			return;
		}
		int mid=curl+curr>>1;
		update(y, node+1, curl, mid);
		update(y, node+(curr-curl&~1), mid, curr);
	}
	void push_back(long long m, long long c){
		update(line(m, c), 0, 0, n);
	}
	long long query(int i, int node, int curl, int curr){
		long long ret=ch[node].eval(x[i]);
		if(curr-curl>1){
			int mid=curl+curr>>1;
			if(i<mid){
				ret=min(ret, query(i, node+1, curl, mid));
			}else{
				ret=min(ret, query(i, node+(curr-curl&~1), mid, curr));
			}
		}
		return ret;
	}
	long long eval(long long test){
		int i=lower_bound(x.begin(), x.end(), test)-x.begin();
		return query(i, 0, 0, n);
	}
};
int main(){
	int n;
	scanf("%d", &n);
	vector<int> h(n), w(n);
	for(int& i: h)
		scanf("%d", &i);
	long long sumw=0;
	for(int& i: w){
		scanf("%d", &i);
		sumw+=i;
		i=-i;
	}
	cht ch(h);
	ch.push_back(-2*h[0], (long long)h[0]*h[0]+w[0]);
	for(int i=1; i+1<n; i++){
		long long cost=ch.eval(h[i]);
		cost+=(long long)h[i]*h[i]+w[i];
		ch.push_back(-2*h[i], (long long)h[i]*h[i]+cost);
	}
	long long ans=ch.eval(h[n-1]);
	ans+=(long long)h[n-1]*h[n-1]+w[n-1]+sumw;
	printf("%lld\n", ans);
}

Compilation message (stderr)

building.cpp: In member function 'void cht::update(cht::line, int, int, int)':
building.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=curl+curr>>1;
      |           ~~~~^~~~~
building.cpp:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   update(y, node+(curr-curl&~1), mid, curr);
      |                   ~~~~^~~~~
building.cpp: In member function 'long long int cht::query(int, int, int, int)':
building.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |    int mid=curl+curr>>1;
      |            ~~~~^~~~~
building.cpp:47:37: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   47 |     ret=min(ret, query(i, node+(curr-curl&~1), mid, curr));
      |                                 ~~~~^~~~~
building.cpp: In function 'int main()':
building.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d", &i);
      |   ~~~~~^~~~~~~~~~
building.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", &i);
      |   ~~~~~^~~~~~~~~~

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