oj.uz

Submission #963796

# Submission time Handle Problem Language Result Execution time Memory
963796 2024-04-15T17:03:01 Z noobcodur Building Bridges (CEOI17_building) C++14
100 / 100
 69 ms 10544 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 = 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;
}

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 1 ms 2400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10544 KB Output is correct
2 Correct 62 ms 10520 KB Output is correct
3 Correct 64 ms 10440 KB Output is correct
4 Correct 62 ms 10444 KB Output is correct
5 Correct 41 ms 8324 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4440 KB Output is correct
5 Correct 1 ms 2400 KB Output is correct
6 Correct 63 ms 10544 KB Output is correct
7 Correct 62 ms 10520 KB Output is correct
8 Correct 64 ms 10440 KB Output is correct
9 Correct 62 ms 10444 KB Output is correct
10 Correct 41 ms 8324 KB Output is correct
11 Correct 69 ms 9672 KB Output is correct
12 Correct 67 ms 9420 KB Output is correct
13 Correct 59 ms 9680 KB Output is correct
14 Correct 64 ms 9564 KB Output is correct
15 Correct 35 ms 10304 KB Output is correct
16 Correct 42 ms 8452 KB Output is correct
17 Correct 30 ms 7624 KB Output is correct
18 Correct 28 ms 7676 KB Output is correct