oj.uz

Submission #128209

# Submission time Handle Problem Language Result Execution time Memory
128209 2019-07-10T14:15:18 Z faustaadp Building Bridges (CEOI17_building) C++17
60 / 100
 1240 ms 9080 KB 
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,a[101010],p[101010],d[101010],w[101010],b[101010],j,has;
set<pair<ll,ll> > st[44];
ll depe(ll aa)
{
	if(aa==n)return 0;
	if(!b[aa])
	{
		b[aa]=1;
		d[aa]=1e18;
		ll ii;
		for(ii=aa+1;ii<=n;ii++)
			d[aa]=min(d[aa],depe(ii)+p[ii-1]-p[aa]+(a[aa]-a[ii])*(a[aa]-a[ii]));
	}
	return d[aa];
}
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)cin>>a[i];
	for(i=1;i<=n;i++)cin>>w[i];
	for(i=1;i<=n;i++)p[i]=p[i-1]+w[i];
	if(n>1000)
	{
		has=(a[1]-a[n])*(a[1]-a[n])+p[n-1]-p[1];
		for(i=2;i<n;i++)
			st[w[i]+20].insert(mp(a[i],i));
		for(i=2;i<n;i++)
			has=min(has,(a[1]-a[i])*(a[1]-a[i])+(a[i]-a[n])*(a[i]-a[n])+p[n-1]-p[i]+p[i-1]-p[1]);
		//cout<<has<<"\n";return 0;
		for(i=2;i<n;i++)
		{
			st[w[i]+20].erase(mp(a[i],i));
			ll hz=(a[1]-a[i])*(a[1]-a[i])+p[i-1]-p[1];
			for(j=-20;j<=20;j++)
			{
				if(st[j+20].empty())continue;
				ll hai=(a[i]+a[n])/2;
				auto it=st[j+20].lower_bound(mp(hai,0));
				ll tom;
				tom=(*it).fi;
				//cout<<i<<" "<<j<<" "<<tom<<" "<<hz+(a[i]-tom)*(a[i]-tom)+(a[n]-tom)*(a[n]-tom)<<" "<<p[n-1]-p[i]-j<<"\n";
				has=min(has,hz+(a[i]-tom)*(a[i]-tom)+(a[n]-tom)*(a[n]-tom)+p[n-1]-p[i]-j);
				it=st[j+20].upper_bound(mp(a[i],0));
				if(it!=st[j+20].begin())
				{
					it--;
					tom=(*it).fi;
					has=min(has,hz+(a[i]-tom)*(a[i]-tom)+(a[n]-tom)*(a[n]-tom)+p[n-1]-p[i]-j);
				}
			}
		//	cout<<hz<<" "<<has<<"\n";
		}
		cout<<has<<"\n";
	}
	else
	{
		cout<<depe(1)<<"\n";
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 9020 KB Output is correct
2 Correct 1174 ms 9080 KB Output is correct
3 Correct 1240 ms 9008 KB Output is correct
4 Correct 312 ms 9080 KB Output is correct
5 Correct 397 ms 8952 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 1192 ms 9020 KB Output is correct
7 Correct 1174 ms 9080 KB Output is correct
8 Correct 1240 ms 9008 KB Output is correct
9 Correct 312 ms 9080 KB Output is correct
10 Correct 397 ms 8952 KB Output is correct
11 Runtime error 30 ms 6520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -