oj.uz

Submission #963725

# Submission time Handle Problem Language Result Execution time Memory
963725 2024-04-15T14:25:12 Z noobcodur Building Bridges (CEOI17_building) C++14
0 / 100
 61 ms 11732 KB 
#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 = INF,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;
}

/*

dp[i] = the min. cost of making a bridge from 1 to i with removing the unnecessary pillars

dp[i] = min(dp[j] + (h[i]-h[j])^2 - w[i])
dp[i] = min(-2*h[j]*h[i] + h[j]^2 + dp[j]) + h[i]^2 - w[i]

*/

Compilation message

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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 11732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -