oj.uz

Submission #870464

# Submission time Handle Problem Language Result Execution time Memory
870464 2023-11-08T02:46:14 Z cpptowin Building Bridges (CEOI17_building) C++17
100 / 100
 38 ms 14864 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf 1000000000
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1 << j))
#define onbit(i, j) (i | (1 << j))
#define vi vector<int>
using namespace std;
using ll = long long;
const ll INFL = 1e18;


struct line {
	ll m, b;
	line() { m = 0, b = INFL; }
	line(ll m, ll b) : m(m), b(b) { }
	ll get(ll x) { return m * x + b; }
};

struct LiChao {
	struct node {
		node *l, *r;
		line x;
		node(line x) : x(x) { l = r = 0; }
	};

	node *t = new node(line());

	void upd(line x, node *&v, int l = 0, int r = maxn) {
		if (!v) { v = new node(x); return; }
		int m = (l + r) / 2;
		bool lf = x.get(l) < v->x.get(l);
		bool md = x.get(m) < v->x.get(m);
		if (md) swap(x, v->x);
		if (l == r) return;
		if (lf != md) upd(x, v->l, l, m);
		else upd(x, v->r, m+1, r);
	}

	ll get(int x, node *&v, int l = 0, int r = maxn) {
		if (!v) return INFL;
		int m = (l + r) / 2;
		if (l == r) return v->x.get(x);
		if (x < m) return min(v->x.get(x), get(x, v->l, l, m));
		else return min(v->x.get(x), get(x, v->r, m+1, r));
	}

	void add(line x) { return upd(x, t); }
	ll get(int x) { return get(x, t); }
}cht;
int n;
int h[maxn];
int w[maxn];
int pre[maxn];
int dp[maxn];
main()
{
   #define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    fo(i, 1, n) cin >> h[i];
    fo(i, 1, n)
    {
        cin >> w[i];
        pre[i] = pre[i - 1] + w[i];
    }
    cht.add({-2 * h[1], h[1] * h[1] - w[1]});
    dp[1] = 0;
    fo(i, 2, n)
    {
        dp[i] = cht.get(h[i]) + pre[i - 1] + h[i] * h[i];
        cht.add({-2 * h[i],h[i] * h[i] - pre[i] + dp[i]});
    }
    cout << dp[n];
}

Compilation message

building.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main()
      | ^~~~
building.cpp: In function 'int main()':
building.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 9872 KB Output is correct
2 Correct 34 ms 10832 KB Output is correct
3 Correct 35 ms 10836 KB Output is correct
4 Correct 32 ms 10332 KB Output is correct
5 Correct 26 ms 13392 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 35 ms 9872 KB Output is correct
7 Correct 34 ms 10832 KB Output is correct
8 Correct 35 ms 10836 KB Output is correct
9 Correct 32 ms 10332 KB Output is correct
10 Correct 26 ms 13392 KB Output is correct
11 Correct 38 ms 11580 KB Output is correct
12 Correct 36 ms 11596 KB Output is correct
13 Correct 27 ms 10504 KB Output is correct
14 Correct 37 ms 11612 KB Output is correct
15 Correct 25 ms 14864 KB Output is correct
16 Correct 26 ms 13396 KB Output is correct
17 Correct 17 ms 10312 KB Output is correct
18 Correct 18 ms 10332 KB Output is correct