oj.uz

Submission #227658

# Submission time Handle Problem Language Result Execution time Memory
227658 2020-04-28T10:09:21 Z nafis_shifat Building Bridges (CEOI17_building) C++14
0 / 100
 181 ms 5048 KB 
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5+7;
vector<ll> m;
vector<ll> b;

ll h[mxn];
ll w[mxn];
ll p[mxn];

ll dp[mxn];

bool bad(int f1,int f2,int f3)
{
	return (b[f3]-b[f1])*(m[f1]-m[f2])<=(b[f2]-b[f1])*(m[f1]-m[f3]);
}

void add(ll m_,ll b_)
{       
	m.push_back(m_);
	b.push_back(b_);
	int sz=m.size();
	while(sz>=3 && bad(sz-3,sz-2,sz-1))
	{
		m.erase(m.end()-2);
		b.erase(b.end()-2);
		sz--;
	}
}

ll func(int p,ll x)
{
	return m[p]*x+b[p];
}
ll query(ll x)
{
    ll ans=1e18;
    int lo=0;
    int hi=m.size()-1;
    while(lo<=hi)
    {
     	int mid1=lo+(hi-lo)/3;
        int mid2=hi-(hi-lo)/3;
        if(func(mid1,x)<func(mid2,x))
        {
            ans=min(ans,func(mid1,x));
            hi=mid2-1;
        }
        else
        {
            ans=min(ans,func(mid2,x));
            lo=mid1+1;
        }
    }
    return ans;
}
     
void solve(int l,int r)
{
	if(l==r)return;
	int mid=l+r>>1;
	solve(l,mid);
	vector<int> v;
	for(int i=l;i<=mid;i++)v.push_back(i);
    m.clear();
    b.clear();
	sort(v.begin(),v.end(),[](int a,int b)
	{
		return h[a]<h[b];
	});

    for(int i=0;i<v.size();i++)
    {
        
    	int k=v[i];
    	add(-2*h[k],dp[k]+h[k]*h[k]-p[k+1]);
    }

    for(int i=mid+1;i<=r;i++)
    {
    	dp[i]=min(dp[i],query(h[i])+h[i]*h[i]+p[i-1]);
    }

    
    solve(mid+1,r);
    

}


int main()
{
    for(int i=1;i<mxn;i++)dp[i]=1e18;
    dp[1]=0;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
	p[0]=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&w[i]);
		p[i]=p[i-1]+w[i];
	}

	solve(1,n);

	cout<<dp[n]<<endl;
	return 0;
}

Compilation message

building.cpp: In function 'void solve(int, int)':
building.cpp:63:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
building.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++)
                 ~^~~~~~~~~
building.cpp: In function 'int main()':
building.cpp:99:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
                       ~~~~~^~~~~~~~~~~~~~
building.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&w[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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