Submission #447835

#	Time	Username	Problem	Language	Result	Execution time	Memory
447835		Killer2501	Building Bridges (CEOI17_building)	C++14	100 / 100	113 ms	89976 KiB

building

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40