Submission #1295745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295745		tdkhai	Building Bridges (CEOI17_building)	C++20	100 / 100	62 ms	66216 KiB

building

/*
        _.-- ,.--.
      .'   .'     /
       @       |'..--------._
     /      \._/              '.
    /  .-.-                     \
   (  /    \                     \
   \\      '.                  | #
    \\       \   -.           /
     :\       |    )._____.'   \
      "       |   /  \  |  \    )
              |   |./'  :__ \.-'
              '--'
*/
#include<bits/stdc++.h>
#define ll long long
#define llll pair<ll,ll>
#define ii pair<int,int>
#define fi first
#define se second
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define ull unsigned long long
#define iii pair<int,ii>
#define iv pair<pii,ii>
#define db double
#define ld long double
#define pb push_back
#define tdk "kfph"

#define int long long
using namespace std;

const int dx[]  = {1, -1, 0, 0};
const int dy[]  = {0, 0, -1, 1};
const int dxx[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyy[] = {2, -2, 2, -2, 1, -1, 1, -1};
const ll INF=1e18;


struct line
{
    ll a,b;
    line(int A=0,int B=0)
    {
        a=A;
        b=B;
    }
    ll calc(ll x)
    {
        return a*x+b;
    }
};
struct lichao
{
    vector<line> st;
    lichao(int sz)
    {
        st.assign(sz*4,line(0,INF));
    }
    void addline(int id,int l,int r,line a)
    {
        if(l==r)
        {
            st[id]=(st[id].calc(l)<a.calc(l)?st[id]:a);
        }
        else
        {
            int mid=l+r>>1;
            if(st[id].calc(mid)>a.calc(mid)) swap(st[id],a);
            if(a.a>st[id].a)
            {
                addline(id*2,l,mid,a);
            }
            if(a.a<st[id].a)
            {
                addline(id*2+1,mid+1,r,a);
            }
        }
    }
    ll query(int id,int l,int r,ll a)
    {
        ll cur=st[id].calc(a);
        if(l==r) return cur;
        int mid=l+r>>1;
        if(a<=mid) return min(cur,query(id*2,l,mid,a));
        else return min(cur,query(id*2+1,mid+1,r,a));
    }
};
const int N=1e6+5;
int n;
ll h[N],w[N];
ll prefix[N],dp[N];
void kfph()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> h[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin >> w[i];
        prefix[i]=prefix[i-1]+w[i];
    }
    const int M=1e6+5;
    lichao tree(M);
    tree.addline(1,1,M,line(-2*h[1],h[1]*h[1]-prefix[1]));
    for(int i=2;i<=n;i++)
    {
        dp[i]=tree.query(1,1,M,h[i])+h[i]*h[i]+prefix[i-1];
        tree.addline(1,1,M,line(-2*h[i],dp[i]+h[i]*h[i]-prefix[i]));
    }
    cout << dp[n];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen(tdk".inp","r"))
    {
        freopen(tdk".inp","r",stdin);
        freopen(tdk".out","w",stdout);
    }
    int t=1;
    //cin >> t;
    while(t--)
    {
        kfph();
    }
    return 0;
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:121:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         freopen(tdk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(tdk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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