Submission #1106089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106089		vukhacminh	Building Bridges (CEOI17_building)	C++17	100 / 100	42 ms	10556 KiB

building

/**
*    Author :  Vu Khac Minh
*    Created : 08.03.2024
**/
#include <bits/stdc++.h>
#define MASK(x) ((1ll) << (x))
#define BIT(x, i) (((x) >> (i)) & (1))
#define c_bit(i) __builtin_popcountll(i)
#define SET_ON(x, i) ((x) | MASK(i))
#define SET_OFF(x, i) ((x) & ~MASK(i))
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = " << (val) << "] "
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9+7;
void file()
{
    #define Task "ROUNDPRI"
    if(fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
}
struct Line {
     mutable ll k, m, p;
     bool operator<(const Line& o) const { return k < o.k; }
     bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
     // (for doubles, use inf = 1/.0, div(a,b) = a/b)
     static const ll inf = LLONG_MAX;
     ll div(ll a, ll b) { // floored division
          return a / b - ((a ^ b) < 0 && a % b); }
     bool isect(iterator x, iterator y) {
          if (y == end()) return x->p = inf, 0;
          if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
          else x->p = div(y->m - x->m, x->k - y->k);
          return x->p >= y->p;
     }
     void addLine(ll k, ll m) {
          auto z = insert({k, m, 0}), y = z++, x = y;
          while (isect(y, z)) z = erase(z);
          if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
          while ((y = x) != begin() && (--x)->p >= y->p)
               isect(x, erase(y));
     }
     ll getValue(ll x) {
          assert(!empty());
          auto l = *lower_bound(x);
          return l.k * x + l.m;
     }
} cht;
ll n,h[maxn],w[maxn],dp[maxn],pre[maxn],a[maxn];
void solve()
{
    cin>>n;
    FOR(i,1,n)
    {
            cin>>h[i];
            if(i>=2) dp[i] = 1e18;
    }
    FOR(i,1,n)
    {
        cin>>a[i];
        pre[i] = pre[i-1] + a[i];
    }
    cht.addLine(2ll*h[1],-(dp[1]+h[1]*h[1]-pre[1]));
    FOR(i,2,n)
    {
        dp[i] = -cht.getValue(h[i]) + h[i]*h[i] + pre[i-1];
        cht.addLine(2*h[i],-(dp[i]+h[i]*h[i]-pre[i]));
    }
    cout<<dp[n];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    file();
    //cin >> ntest;
    while (ntest--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

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

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