oj.uz

답안 #903947

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
903947 2024-01-11T15:15:29 Z Flan312 Building Bridges (CEOI17_building) C++17
0 / 100
 51 ms 7008 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task ""
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 1e5 + 2;
const ll oo = 1e18;
int n;
ll h[nmax], w[nmax], dp[nmax];
struct segment
{
    ll a, b;
    segment(ll a = 0, ll b = oo) : a(a), b(b) {}
};
struct node
{
    segment line;
    node *l, *r;
    node(const segment &line = segment(), node *l = nullptr, node *r = nullptr) : line(line), l(l), r(r) {}
};
#define check(x) if (x == nullptr) x = new node()
node *lichao = new node();
ll get(const segment &line, int x)
{
    return line.a * x + line.b;
}
void update(node *root, int l, int r, int u, int v, const segment &line)
{
    if (l > v || r < u) return;
    int mid = l + r >> 1;
    if (l >= u && r <= v)
    {
        check(root -> l);
        check(root -> r);
        //6 case, lichao min
        ll rootL = get(root -> line, l);
        ll rootR = get(root -> line, r);
        ll rootM = get(root -> line, mid);
        ll lineL = get(line, l);
        ll lineR = get(line, r);
        ll lineM = get(line, mid);
        if (rootL <= lineL && rootR <= lineR) return;
        if (rootL >= lineL && rootR >= lineR) {root -> line = line; return;}
        if (rootL <= lineL && rootM <= lineM)
        {
            update(root -> r, mid + 1, r, u, v, line);
            return;
        }
        if (rootL >= lineL && rootM >= lineM)
        {
            update(root -> r, mid + 1, r, u, v, root -> line);
            root -> line = line;
            return;
        }
        if (get(root -> line, mid + 1) <= get(line, mid + 1) && rootR <= lineR)
        {
            update(root -> l, l, mid, u, v, line);
            return;
        }
        if (get(root -> line, mid + 1) >= get(line, mid + 1) && rootR >= lineR)
        {
            update(root -> l, l, mid, u, v, root -> line);
            root -> line = line;
            return;
        }
    }
    update(root -> l, l, mid, u, v, line);
    update(root -> r, mid + 1, r, u, v, line);
}
void update(int u, int v, const segment &line) {update(lichao, 1, 2e6, 1, 2e6, line);}
ll get(node *root, int l, int r, int x)
{
    if (root == nullptr || (l > x || r < x)) return oo;
    ll res = get(root -> line, x);
    if (l == r) return res;
    int mid = l + r >> 1;
    res = min(res, get(root -> l, l, mid, x));
    res = min(res, get(root -> r, mid + 1, r, x));
    return res;
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
        cin >> w[i];;
    dp[1] = -w[1];
    update(1, 2e6, segment(-2 * h[1], 1ll * h[1] * h[1] + dp[1]));
    for (int i = 2; i <= n; ++i)
    {
        dp[i] = 1ll * h[i] * h[i] - w[i] + get(lichao, 1, 2e6, h[i]);
        update(1, 2e6, segment(-2 * h[i], 1ll * h[i] * h[i] + dp[i]));
    }
    cout << dp[n] + accumulate(w + 1, w + n + 1, 0LL);
}

Compilation message

building.cpp: In function 'void update(node*, int, int, int, int, const segment&)':
building.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'long long int get(node*, int, int, int)':
building.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'int main()':
building.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
   90 |     if (ifstream(task".inp")) nx
      |                               ^~
building.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp:90:31: note: in expansion of macro 'nx'
   90 |     if (ifstream(task".inp")) nx
      |                               ^~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Incorrect 1 ms 2408 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4292 KB Output is correct
2 Correct 45 ms 4200 KB Output is correct
3 Correct 45 ms 4200 KB Output is correct
4 Correct 51 ms 3936 KB Output is correct
5 Incorrect 49 ms 7008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2524 KB Output is correct
3 Incorrect 1 ms 2408 KB Output isn't correct
4 Halted 0 ms 0 KB -