Submission #1187171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187171		sitingfake	Building Bridges (CEOI17_building)	C++20	100 / 100	42 ms	8308 KiB

building

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s";
#define ll long long
#define ld long double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b;return 1;}
    return 0;
}

//constant

const ll mod = 1e9+7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6+5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};


//code
const int maxn = 1e5 + 7;

ll h[maxn],pre[maxn];

int n;

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) {
        iterator 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));
    }
    void Free()
    {
        while(!empty())
        {
            erase(begin());
        }
        return;
    }
    ll get(ll x) {
        assert(!empty());
        Line l = *lower_bound(x);
        return l.k * x + l.m;
    }
    /**
    notice : this is LineContainer for Max Query, however, if we need Min Query just add the "-"
    in our AddLine and answer
    exp : cht.AddLine(-a,-b) for Min Q; ans = - cht.get(x)
    when query x the Line gives us maximum ans for x , our ans just ans = - ans
    **/
};

void solve(void)
{
    cin >> n;

    for(int i=1;i<=n;i++)
    {
        cin >> h[i];
    }

    for(int i=1;i<=n;i++)
    {
        int x; cin >> x;
        pre[i] = pre[i-1] + x;
    }

    LineContainer cht;

    cht.AddLine(2 * h[1], -(h[1] * h[1] - pre[1]));

    for(int i=2;i<=n;i++)
    {
        ll tmp = -cht.get(h[i]) + pre[i-1] + h[i] * h[i];
        cht.AddLine(2 * h[i],-(tmp + h[i] * h[i] - pre[i]));
        if(i == n) cout << tmp;
    }

}

signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc; tc = 1;

   while(tc--) solve();

   //execute;
}

/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/

Compilation message (stderr)

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

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