oj.uz

Submission #447835

# Submission time Handle Problem Language Result Execution time Memory
447835 2021-07-27T16:36:02 Z Killer2501 Building Bridges (CEOI17_building) C++14
100 / 100
 113 ms 89976 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+1;
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 == r)return;
    if(ok1 != ok2)add(id*2, l, mid, d);
    else add(id*2+1, mid+1, 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 == r)return res;
    if(mid >= x)return min(res, get(id*2, l, mid, x));
    else return min(res, get(id*2+1, mid+1, 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();

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

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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86328 KB Output is correct
2 Correct 43 ms 86388 KB Output is correct
3 Correct 43 ms 86348 KB Output is correct
4 Correct 45 ms 86400 KB Output is correct
5 Correct 60 ms 86404 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 89808 KB Output is correct
2 Correct 96 ms 89804 KB Output is correct
3 Correct 94 ms 89704 KB Output is correct
4 Correct 96 ms 89668 KB Output is correct
5 Correct 88 ms 89712 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86328 KB Output is correct
2 Correct 43 ms 86388 KB Output is correct
3 Correct 43 ms 86348 KB Output is correct
4 Correct 45 ms 86400 KB Output is correct
5 Correct 60 ms 86404 KB Output is correct
6 Correct 102 ms 89808 KB Output is correct
7 Correct 96 ms 89804 KB Output is correct
8 Correct 94 ms 89704 KB Output is correct
9 Correct 96 ms 89668 KB Output is correct
10 Correct 88 ms 89712 KB Output is correct
11 Correct 110 ms 89976 KB Output is correct
12 Correct 100 ms 89732 KB Output is correct
13 Correct 88 ms 89784 KB Output is correct
14 Correct 113 ms 89880 KB Output is correct
15 Correct 86 ms 89576 KB Output is correct
16 Correct 98 ms 89668 KB Output is correct
17 Correct 79 ms 89796 KB Output is correct
18 Correct 78 ms 89836 KB Output is correct