Submission #152811

#	Time	Username	Problem	Language	Result	Execution time	Memory
152811		Mercenary	Building Bridges (CEOI17_building)	C++14	100 / 100	188 ms	8276 KiB

building

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int maxn = 1e5 + 5;
const int logn = 18;

struct point{
    ll x , y;
    point(){};
    point(ll x , ll y):x(x) , y(y){};
    point operator + (point other){
        return point(x + other.x , y + other.y);
    }
    point operator - (point other){
        return point(x - other.x , y - other.y);
    }
    ld operator % (point other){
        return (ld)x * other.y - (ld)y * other.x;
    }
    bool operator < (point other){
        if(x == other.x)return y < other.y;
        return x > other.x;
    }
};

void build(vector<point> & s){
    vector<point> res;
    sort(s.begin(),s.end());
    int m = 0;
    for(point c : s){
        if(m >= 1 && res[m - 1].x == c.x && res[m - 1].y < c.y)continue;
        if(m >= 2 && (res[m - 1] - res[m - 2]) % (res[m - 1] - c) <= 0)--m , res.pop_back();
        ++m;res.pb(c);
    }
    s = res;
}

ll ans(vector<point> & s , ll x){
    if(s.size() == 0)return (ll)1e18;
    int l = 0 , h = s.size() - 1;
    while(l < h){
        int mid = l + h >> 1;
        if(s[mid].x * x + s[mid].y >= s[mid + 1].x * x + s[mid + 1].y)l = mid + 1;
        else h = mid;
    }
    return s[l].x * x + s[l].y;
}

void debug(vector<point> &s , ll x , ll y){
    for(point c : s){
        cout <<  c.x << " " << c.y << " " << x << " " << c.x * x + c.y + y << endl;
    }
    cout << endl;
}

vector<point> s[logn];

void add(point x){
    int build = 0;
    for(int i = 0 ; i < logn ; ++i){
        if(s[i].size() == 0){
            build = i;
            break;
        }
    }
    s[0].pb(x);
    for(int i = 0 ; i < build ; ++i){
        for(point & c : s[i])s[i + 1].pb(c);
        ::build(s[i + 1]);
        s[i].clear();
    }
    ::build(s[build]);
}

int n;
int h[maxn];
ll w[maxn] , dp[maxn];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)cin >> h[i];
    for(int i = 1 ; i <= n ; ++i){
        cin >> w[i];
        w[i] += w[i - 1];
    }
    for(int i = 2 ; i <= n ; ++i){
        add(point(2 * h[i - 1] , (ll)h[i - 1] * h[i - 1] - w[i - 1] + dp[i - 1]));
        dp[i] = 1e18;
        for(int j = 0 ; j < logn ; ++j){
            dp[i] = min(dp[i] , ans(s[j] , -h[i]) + w[i - 1] + (ll)h[i] * h[i]);
//            if(i == 97){
//                debug(s[j] , -h[i] , + w[i - 1] + (ll)h[i] * h[i]);
//            }
//            if(i == 97){
//                cout << ans(s[j] , -h[i]) + w[i - 1] + (ll)h[i] * h[i] << endl;
//            }
        }
//        cout << dp[i] << endl;
    }
    cout << dp[n];
}

Compilation message (stderr)

building.cpp: In function 'll ans(std::vector<point>&, ll)':
building.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~
building.cpp: In function 'int main()':
building.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:94:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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