Submission #685218

#	Time	Username	Problem	Language	Result	Execution time	Memory
685218		Quan2003	Building Bridges (CEOI17_building)	C++17	100 / 100	86 ms	19184 KiB

building

#include <bits/stdc++.h>
#include <iostream> 
#include<vector>
using namespace std;
typedef long long ll;
const int sz = 4e5 + 1;
const int N = 4e5 + 5;
const int M = 4e5 + 5;
const int mod = 1e9 + 7; 
long long n,m,k,q,cnt;
long long w[N + 1];
long long h[N + 1];
long long dp[N + 1];
vector<int>adj[N + 1]; 
bool _Line_Comp_State; 
struct Line {
	// k is slope, m is intercept, p is intersection point
	mutable long long k, m, p;
	bool operator<(const Line& o) const {
		return _Line_Comp_State ? p < o.p : k < o.k;
	}
};
struct LineContainer : multiset<Line> {
	long long div(long long a, long long b) { return a / b - ((a ^ b) < 0 && a % b); }

	bool isect(iterator x, iterator y) {
		if (y == end()) { 
			x->p = LLONG_MAX; 
			return false; 
		}
		if (x->k == y->k) {
			x->p = x->m > y->m ? LLONG_MAX : -LLONG_MAX;
		} else {
			x->p = div(y->m - x->m, x->k - y->k);
		}
		return x->p >= y->p;
	}
	void add(long long k, long long m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) {
			z = erase(z);
		}
		if (x != begin() && isect(--x, y)) {
			isect(x, y = erase(y));
		}
		while ((y = x) != begin() && (--x)->p >= y->p) {
			isect(x, erase(y));
		}
	}

	long long query(long long x) {
		assert(!empty());
		_Line_Comp_State = 1; 
		auto l = *lower_bound({0, 0, x}); 
		_Line_Comp_State = 0;
		return l.k * x + l.m;
	}
};
int main(){
     scanf("%d",&n);
     long long to = 0;
     for(int i = 1; i <= n; i++) cin>>h[i];
     for(int i = 1; i <= n; i++){
          cin>>w[i];
          to += w[i];
     }
     LineContainer lc;
     dp[1] = -w[1];
     lc.add(2 * h[1], -(long long) h[1] * h[1] - dp[1]); 
     for(int i = 2; i <= n; i++){
          dp[i] =  - lc.query(h[i]) - w[i] + (long long) h[i] * h[i];
          lc.add(2 * h[i],  -(long long) h[i] * h[i] - dp[i]);
     }
     cout<<dp[n] + to<<endl; 
} 

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:60:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   60 |      scanf("%d",&n);
      |             ~^  ~~
      |              |  |
      |              |  long long int*
      |              int*
      |             %lld
building.cpp:60:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |      scanf("%d",&n);
      |      ~~~~~^~~~~~~~~

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