Submission #154283

#	Time	Username	Problem	Language	Result	Execution time	Memory
154283		arnold518	Building Bridges (CEOI17_building)	C++14	100 / 100	88 ms	10616 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXH = 1e6;
const ll INF = 1e15;

int N;
ll H[MAXN+10], W[MAXN+10];
ll dp[MAXN+10];

struct Node
{
    ll a, b;
    Node *lc, *rc;
    Node() : a(0), b(INF), lc(NULL), rc(NULL) {}
};

void update(Node *node, int tl, int tr, ll a, ll b)
{
    int mid=tl+tr>>1;
    ll fl=node->a*tl+node->b, fr=node->a*tr+node->b;
    ll nfl=a*tl+b, nfr=a*tr+b;

    if(fl>=nfl && fr>=nfr) { node->a=a; node->b=b; return; }
    if(fl<=nfl && fr<=nfr) return;
    if(node->lc==NULL) node->lc=new Node();
    if(node->rc==NULL) node->rc=new Node();
    update(node->lc, tl, mid, a, b);
    update(node->rc, mid+1, tr, a, b);
}

ll query(Node *node, int tl, int tr, int pos)
{
    if(node==NULL) return INF;
    int mid=tl+tr>>1;
    ll now=node->a*pos+node->b;
    if(pos<=mid) return min(now, query(node->lc, tl, mid, pos));
    else return min(now, query(node->rc, mid+1, tr, pos));
}

Node *root=new Node();

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%lld", &H[i]);
    for(i=1; i<=N; i++) scanf("%lld", &W[i]), W[i]+=W[i-1];

    dp[1]=0;
    update(root, 0, MAXH, -2*H[1], dp[1]+H[1]*H[1]-W[1]);
    for(i=2; i<=N; i++)
    {
        dp[i]=query(root, 0, MAXH, H[i])+W[i-1]+H[i]*H[i];
        update(root, 0, MAXH, -2*H[i], dp[i]+H[i]*H[i]-W[i]);
    }
    printf("%lld", dp[N]);
}

Compilation message (stderr)

building.cpp: In function 'void update(Node*, int, int, ll, ll)':
building.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
building.cpp: In function 'll query(Node*, int, int, int)':
building.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
building.cpp: In function 'int main()':
building.cpp:50:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
building.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
building.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &H[i]);
                         ~~~~~^~~~~~~~~~~~~~~
building.cpp:54:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%lld", &W[i]), W[i]+=W[i-1];
                         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40