oj.uz

Submission #472452

# Submission time Handle Problem Language Result Execution time Memory
472452 2021-09-13T15:28:38 Z Killer2501 Building Bridges (CEOI17_building) C++14
100 / 100
 103 ms 89972 KB 
#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "fencing"
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second
#define mp make_pair
 
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1e15+7;
const int sz = 1e6+5;
using namespace std;
const int N = 1e6 + 5;
ll m, n, k, tong, t, T, ans;
ll dp[N], pos[N], a[N], b[N], c[N];
string s;
vector<ll> kq, adj[N];
struct node
{
     ll x, y;
     node(){}
     node(ll x, ll y): x(x), y(y){};
     ll get(ll t)
     {
         return x * t + y;
     }
}st[N*4];
void add(ll id, ll l, ll r, node d)
{
    ll mid = (l + r) / 2;
    bool ok1 = d.get(mid) < st[id].get(mid);
    bool ok2 = d.get(l) < st[id].get(l);
    if(ok1)swap(st[id], d);
    if(l+1 == r)return;
    if(ok1 != ok2)add(id*2, l, mid, d);
    else add(id*2+1, mid, r, d);
}
ll get(ll id, ll l, ll r, ll x)
{
    ll mid = (l + r) / 2;
    ll res = st[id].get(x);
    if(l+1 == r)return res;
    if(x < mid)return min(res, get(id*2, l, mid, x));
    else return min(res, get(id*2+1, mid, r, x));
}
void sol()
{
    cin >> n;
    for(int i = 1; i <= 4*sz; i ++)st[i] = node(0, mod);
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 1; i <= n; i ++)
    {
        cin >> b[i];
        c[i] = c[i-1] + b[i];
    }
    add(1, 1, sz, node(-2*a[1], a[1] * a[1] - c[1]));
    for(int i = 2; i <= n; i ++)
    {
        ans = get(1, 1, sz, a[i]) + a[i] * a[i] + c[i-1];
        add(1, 1, sz, node(-2*a[i], ans - c[i] + a[i] * a[i]));
    }
    cout << ans;
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".in", "r"))
    {
		freopen(task".in","r",stdin);
		freopen(task".out","w",stdout);
    }
    sol();
 
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen(task".in","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
building.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen(task".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
building.cpp: In function 'void sol()':
building.cpp:53:42: warning: iteration 4000019 invokes undefined behavior [-Waggressive-loop-optimizations]
   53 |     for(int i = 1; i <= 4*sz; i ++)st[i] = node(0, mod);
      |                                    ~~~~~~^~~~~~~~~~~~~~
building.cpp:53:22: note: within this loop
   53 |     for(int i = 1; i <= 4*sz; i ++)st[i] = node(0, mod);
      |                    ~~^~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 86336 KB Output is correct
2 Correct 41 ms 86364 KB Output is correct
3 Correct 47 ms 86360 KB Output is correct
4 Correct 43 ms 86436 KB Output is correct
5 Correct 43 ms 86396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 89772 KB Output is correct
2 Correct 94 ms 89760 KB Output is correct
3 Correct 92 ms 89788 KB Output is correct
4 Correct 88 ms 89660 KB Output is correct
5 Correct 89 ms 89792 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 86336 KB Output is correct
2 Correct 41 ms 86364 KB Output is correct
3 Correct 47 ms 86360 KB Output is correct
4 Correct 43 ms 86436 KB Output is correct
5 Correct 43 ms 86396 KB Output is correct
6 Correct 91 ms 89772 KB Output is correct
7 Correct 94 ms 89760 KB Output is correct
8 Correct 92 ms 89788 KB Output is correct
9 Correct 88 ms 89660 KB Output is correct
10 Correct 89 ms 89792 KB Output is correct
11 Correct 103 ms 89972 KB Output is correct
12 Correct 101 ms 89668 KB Output is correct
13 Correct 86 ms 89796 KB Output is correct
14 Correct 100 ms 89824 KB Output is correct
15 Correct 87 ms 89540 KB Output is correct
16 Correct 86 ms 89600 KB Output is correct
17 Correct 76 ms 89796 KB Output is correct
18 Correct 82 ms 89796 KB Output is correct