Submission #1309839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309839		ibrooosh	Building Bridges (CEOI17_building)	C++20	30 / 100	3090 ms	2564 KiB

building

// #pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}

#define du long double
#define m_p make_pair
#define pb push_back
#define pii pair<int,int>
#define piii pair<pii,int>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<pair<int,pii> >
#define si set<int>
#define sii multiset<pii>
#define siii set<pair<int,pii> >
#define F first
#define S second
#define pre precision
#define sz size()
#define all(x) x.begin(),x.end()
#ifndef ONLINE_JUDGE
#define OK  cout << __LINE__ << "| "<< "---------------------------OK-----------------------" << endl;
#define deb(x) cout << __LINE__ << "| "<< #x  << " = " << x << endl;
#else
#define OK  
#define deb(x) 
#endif
#define int long long
#define cn continue
#define rt return
#define nl cout<<'\n'
#define OPEN  freopen ("exam.in","r" , stdin), freopen ("exam.out","w",stdout)
const ll mod=1e9+7;
const ll inf=1e18;
const du PI=3.14;
const int N=1e6;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
ll f[N];

ll phi(ll n){
	ll res = n;
	for(ll i = 2; i * i <= n; i ++){
		if(n % i == 0){
			while(n % i == 0)
				n /= i;
			res -= res / i;
		}
	}
	if(n > 1)
		res -= res / n;
	return res;
}
ll bp(ll a,ll b){
		ll res=1;
		while(b){
			if(b&1)res=(res%mod)*(a%mod);
			res%=mod;
			a=a*a%mod;
			b/=2ll;
		}
		return res;
}
ll mult(ll a,ll b){
	return (1ll*a*b)%mod;
}
ll di(ll a,ll b){
	return mult(a,bp(b,phi(mod)-1));
}
ll add (ll a,ll b){
	a+=b;
	if(a>=mod)a-=mod;
	return a;
}
ll sub(ll a,ll b){
	a-=b;
	if(a<0)a+=mod;
	return a;
}
int dp[N];
int a[N];
int n;
int w[N],h[N];
void Teemka_abi(){
	cin>>n;
	int all=0;
	for(int i=1;i<=n;i++){
		cin>>h[i];
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
		all+=w[i];
	}
	for(int i=2;i<=n;i++){
		dp[i]=1e9;
	}
	dp[1]=-w[1];
	for(int i=2;i<=n;i++){
		// dp[i]=dp[i-1];
		for(int j=1;j<i;j++){
			dp[i]=min(dp[i],dp[j]+(h[i]-h[j])*(h[i]-h[j])-w[i]);
		}
	}
	cout<<dp[n]+all;
}
signed main(){
	
	// OPEN;	
	int tt=1;
	// cin>>tt;
	while(tt--){
		Teemka_abi();
		nl;
	}
}

Compilation message (stderr)

building.cpp:41: warning: "int" redefined
   41 | #define int long long
      | 
building.cpp:5: note: this is the location of the previous definition
    5 | #define int ll
      |

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