Submission #152787

#	Time	Username	Problem	Language	Result	Execution time	Memory
152787		Mercenary	Building Bridges (CEOI17_building)	C++14	0 / 100	92 ms	6104 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 = 17;

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);
    }
    ll operator % (point other){
        return x * other.y - 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(res.begin(),res.end());
    int m = 0;
    for(point c : s){
        if(m >= 2 && (res[m - 2] - res[m - 1]) % (c - res[m - 1]) >= 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(mid + 1 < s.size() &&
           s[mid].x * x + s[mid].y >= s[mid + 1].x * x + s[mid + 1].y)l = mid + 1;
        else h = mid - 1;
    }
//    cout << s.size() << " " << l << endl;
    return s[l].x * x + s[l].y;
}

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;
        }
    }
    for(int i = 0 ; i < build ; ++i){
        for(point & c : s[i])s[build].pb(c);
        s[i].clear();
    }
    s[build].pb(x);
    ::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]);
        }
//        cout << dp[i] << endl;
    }
    cout << dp[n];
}

Compilation message (stderr)

building.cpp: In function 'll ans(std::vector<point>&, ll)':
building.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + h >> 1;
                   ~~^~~
building.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mid + 1 < s.size() &&
            ~~~~~~~~^~~~~~~~~~
building.cpp: In function 'int main()':
building.cpp:86: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:87: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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40