Submission #1245300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245300		escobrand	Building Bridges (CEOI17_building)	C++20	100 / 100	41 ms	10564 KiB

building

#include <bits/stdc++.h>

using namespace std;
#define se second
#define fi first
#define ll long long 
#define all(a) a.begin(),a.end()
#define eb push_back
#define ld long double
int i,n,t;
const ld inf = 1e8;
const int maxn = 1e5 + 10;
ll a[maxn],pre[maxn],dp[maxn];

struct line
{
  ll a,b;
  mutable ld p;
  line():a(0),b(0),p(-inf){};
  line(ll A,ll B):a(A),b(B),p(-inf){};
  
  ll cal(ll x)const{return a * x +b;}
  bool operator < (const ll &x)const {return p < x;}
  bool operator < (const line & tmp)const{return (a != tmp.a?a>tmp.a : b<tmp.b);}
};

struct LC : multiset<line,less<void>> {
  ld xcut(iterator x,iterator y){return (ld)(y->b - x->b) / (x->a  - y->a);}
  
  bool check(iterator x,iterator y)
  {
    if(y == end())return x->p = inf,1;
    if(x->a == y->a)return 0;
    return ((x->p = xcut(x,y)) < y->p);
  }
  
  void add(ll a,ll b)
  {
    iterator x = emplace(a,b);
    iterator y = next(x);
    while(!check(x,y))y = erase(y);
    if(x != begin())
    {
      y = prev(x);
      if(!check(y,x))check(y,erase(x));
    }
    else return;
    
    while(y != begin())
    {
      x = prev(y);
      if(x->p >= y->p)check(x,erase(y)),y = x;
      else break;
    }
  }
  
  ll cal(ll x){return lower_bound(x)->cal(x);}
}lc;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(i =1;i<=n;i++)
    {
      cin>>a[i];
    }
    for(i =1;i<=n;i++)
    {
      cin>>pre[i];
      pre[i] += pre[i-1];
      if(i == 1)
      {
        dp[i] = 0;
      }
      else 
      {
        dp[i] = lc.cal(a[i]) + a[i] * a[i] + pre[i-1];
      }
      lc.add(-2 * a[i],a[i] * a[i] + dp[i] - pre[i]);
    }
    cout<<dp[n];
    
    return 0;
}

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