oj.uz

Submission #486295

# Submission time Handle Problem Language Result Execution time Memory
486295 2021-11-11T08:05:59 Z kiomi Building Bridges (CEOI17_building) C++14
60 / 100
 834 ms 13352 KB 
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")

//#pragma comment(linker,"/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define full(x,n) x,x+n+1
#define full(x) x.begin(),x.end()
#define finish return 0

#define putb push_back
#define f first
#define s second

//logx(a^n)=loga(a^n)/logx(a)
//logx(a*b)=logx(a)+logx(b)
//logx(y)=log(y)/log(x)
//logb(n)=loga(n)/loga(b)

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define putf push_front
#define gainb pop_back

//(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n
//(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i

#define gainf pop_front
#define len(x) (int)x.size()

// 1/b%mod=b^(m-2)%mod
// (a>>x)&1==0
// a^b=(a+b)-2(a&b)

typedef double db;
typedef long long ll;

//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)

const int ary=1e6+5;
const ll mod=1e9+7;
const ll inf=1e18;

using namespace std;
using namespace __gnu_pbds;
int n;
ll h[ary],w[ary];
ll dp[ary],p[ary];
bool t[41][4*ary];
void upd(int x,int p,int v=1,int tl=0,int tr=ary-5){
	if(p>tr||p<tl){
		return;
	}
	if(tl==tr){
		t[x][v]=1;
		return;
	}
	int tm=(tl+tr)/2;
	upd(x,p,v*2,tl,tm);
	upd(x,p,v*2+1,tm+1,tr);
	t[x][v]=(t[x][v*2]||t[x][v*2+1]);
}
int get1(int x,int p,int v=1,int tl=0,int tr=ary-5){
	if(tl>p||!t[x][v]){
		return -1;
	}
	if(tl==tr){
		return tl;
	}
	int tm=(tl+tr)/2;
	int a=get1(x,p,v*2+1,tm+1,tr);
	if(a!=-1){
		return a;
	}
	return get1(x,p,v*2,tl,tm);
}
int get2(int x,int p,int v=1,int tl=0,int tr=ary-5){
	if(tr<p||!t[x][v]){
		return -1;
	}
	if(tl==tr){
		return tl;
	}
	int tm=(tl+tr)/2;
	int a=get2(x,p,v*2,tl,tm);
	if(a!=-1){
		return a;
	}
	return get2(x,p,v*2+1,tm+1,tr);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		p[i]=p[i-1]+w[i];
	}
	if(n>1000){
		for(int i=1;i<n;i++){
			if(i==1){
				dp[n]=p[n-1]-p[1]+(h[n]-h[1])*(h[n]-h[1]);	
			}
			else{
				dp[n]=min(dp[n],p[n-1]-p[1]-w[i]+(h[n]-h[i])*(h[n]-h[i])+(h[i]-h[1])*(h[i]-h[1]));
				if(i>2){
					int k=(h[i]+h[1])/2;
					for(int j=-20;j<=20;j++){
						ll a=get1(j+20,k);
						if(a!=-1){
							dp[n]=min(dp[n],p[n-1]-p[1]-w[i]-j+(h[n]-h[i])*(h[n]-h[i])+(h[i]-a)*(h[i]-a)+(a-h[1])*(a-h[1]));
						}
						a=get2(j+20,k+1);
						if(a!=-1){
							dp[n]=min(dp[n],p[n-1]-p[1]-w[i]-j+(h[n]-h[i])*(h[n]-h[i])+(h[i]-a)*(h[i]-a)+(a-h[1])*(a-h[1]));
						}
					}
				}
				upd(w[i]+20,h[i]);
			}
		}
		cout<<dp[n];
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(i>1){
			dp[i]=p[i-1]-p[1]+(h[i]-h[1])*(h[i]-h[1]);
		}
		for(int j=2;j<i;j++){
			dp[i]=min(dp[i],dp[j]+p[i-1]-p[j]+(h[i]-h[j])*(h[i]-h[j]));
		}
	}
	cout<<dp[n];
}

Compilation message

building.cpp:15: warning: "full" redefined
   15 | #define full(x) x.begin(),x.end()
      | 
building.cpp:14: note: this is the location of the previous definition
   14 | #define full(x,n) x,x+n+1
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 4620 KB Output is correct
2 Correct 804 ms 4992 KB Output is correct
3 Correct 834 ms 5000 KB Output is correct
4 Correct 126 ms 3276 KB Output is correct
5 Correct 818 ms 13352 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 812 ms 4620 KB Output is correct
7 Correct 804 ms 4992 KB Output is correct
8 Correct 834 ms 5000 KB Output is correct
9 Correct 126 ms 3276 KB Output is correct
10 Correct 818 ms 13352 KB Output is correct
11 Runtime error 21 ms 5656 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -