oj.uz

Submission #1106089

# Submission time Handle Problem Language Result Execution time Memory
1106089 2024-10-29T08:10:03 Z vukhacminh Building Bridges (CEOI17_building) C++17
100 / 100
 42 ms 10556 KB 
/**
*    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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2 ms 2556 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4688 KB Output is correct
2 Correct 27 ms 4688 KB Output is correct
3 Correct 31 ms 4680 KB Output is correct
4 Correct 25 ms 4604 KB Output is correct
5 Correct 24 ms 5712 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2520 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 2 ms 2556 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 28 ms 4688 KB Output is correct
7 Correct 27 ms 4688 KB Output is correct
8 Correct 31 ms 4680 KB Output is correct
9 Correct 25 ms 4604 KB Output is correct
10 Correct 24 ms 5712 KB Output is correct
11 Correct 27 ms 4688 KB Output is correct
12 Correct 30 ms 4432 KB Output is correct
13 Correct 21 ms 4688 KB Output is correct
14 Correct 34 ms 4688 KB Output is correct
15 Correct 42 ms 10556 KB Output is correct
16 Correct 28 ms 5704 KB Output is correct
17 Correct 14 ms 4432 KB Output is correct
18 Correct 14 ms 4676 KB Output is correct