제출 #963796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963796		noobcodur	Building Bridges (CEOI17_building)	C++14	100 / 100	69 ms	10544 KiB

building

#include<bits/stdc++.h>
using namespace std;
 
using ld = long double;
 
#define int long long
#define pii pair<int,int>
#define forn(i,j) for(int i = 0; i < j; ++i)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
 
const int MOD = 1e9+7; const int INF = 1e17+1; const int maxN = 2e5+1;
 
void setIO(string name){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	if(!name.empty()){
		freopen((name + ".in").c_str(),"r",stdin);
		freopen((name + ".out").c_str(),"w",stdout);
	}
}
 
int val[maxN],h[maxN],w[maxN];
 
struct Line{
	int m = 0,c = INF;
 
	int operator()(int x){
		return m*val[x] + c;
	}
};
 
Line st[4*maxN];
 
void insert(int pos, int l, int r, Line L){
	if(l == r){
		if(L(l) < st[pos](l)) st[pos] = L;
 
		return;
	}
 
	int mid = (l+r)/2;
 
	if(st[pos].m < L.m) swap(st[pos],L);
 
	if(st[pos](mid) > L(mid)){
		swap(st[pos],L);
 
		insert(2*pos,l,mid,L);
		return;
	}
 
	insert(2*pos+1,mid+1,r,L);
}
 
int query(int pos, int l, int r, int x){
	if(l == r){
		return st[pos](x);
	}
 
	int mid = (l+r)/2;
 
	if(x > mid) return min(st[pos](x),query(2*pos+1,mid+1,r,x));
 
	return min(st[pos](x),query(2*pos,l,mid,x));
}
 
int dp[maxN];
 
signed main(){
	setIO("");
	int n; cin >> n;
	vi nums;
	int tot = 0;
 
	forn(i,n){
		cin >> h[i];
		nums.pb(h[i]);
	}
 
	sort(all(nums));
 
	forn(i,n){
		val[i] = nums[i];
	}
 
	forn(i,n){
		cin >> w[i];
		tot += w[i];
	}
 
	dp[0] = -w[0];
	Line C = {-2*h[0],h[0]*h[0]+dp[0]};
 
	insert(1,0,n-1,C);
 
	forrange(i,1,n){
		int idx = lower_bound(all(nums),h[i]) - nums.begin();
		dp[i] = query(1,0,n-1,idx) + h[i]*h[i] - w[i];
		Line D = {-2*h[i],h[i]*h[i]+dp[i]};
 
		insert(1,0,n-1,D);
	}
 
	cout << tot + dp[n-1] << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

building.cpp: In function 'void setIO(std::string)':
building.cpp:24:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   freopen((name + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:25:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   freopen((name + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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