Submission #534598

#	Time	Username	Problem	Language	Result	Execution time	Memory
534598		David_M	Aliens (IOI16_aliens)	C++14	100 / 100	297 ms	11928 KiB

aliens

//#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


deque<pair<pll, int> > dq;
int o=0;

bool check (ll k, ll b){
    int e=dq.size();
    auto [k0,b0]=dq[e-1].F;
    auto [k1,b1]=dq[e-2].F;

//    k1 * x + b1 = k0 * x + b0
//    (b0 - b1) / (k1 - k0)
//    k1 * x + b1 = k * x + b
//    (b - b1) / (k1 - k)
//
//    k < k0 < k1
//
//    (b - b1) / (k1 - k) > (b0 - b1) / (k1 - k0)
//    (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) > 0

    return (b - b1) * (k1 - k0) - (b0 - b1) * (k1 - k) < 0;
}

void add(ll k, ll b, int cnt){
    while(dq.size()>1 && check(k, b))dq.pop_back();
    dq.push_back({{k,b},cnt});
}

pll get(int i, ll x, ll C){
    if(i==dq.size()){
        return {100000000000009, 100000000000009};
    }
    auto [k,b]=dq[i].F;
//    cout<<"[i, k, b, x]: "<<i<<" "<<dq.size()<<" "<<k<<" "<<b<<" "<<x<<endl;
    return {k*x+b, dq[i].S};
}

void calc_dp(int n, vector<pll> v, vector<pll> &dp, ll C){
        dp[0]={0,0};
        add(v[0].F*-2, v[0].F*v[0].F, 0);
        for (int i=1; i<=n; i++){
            auto &[ans, cnt]=dp[i];
            ll r=v[i-1].S;
            ans=r*r+C;
//            cout<<"[ans]: "<<ans<<endl;
            cnt=1;
            ll x=r;
            o=min((int)dq.size()-1, o);
            while(i>1 && get(o,x,C)>get(o+1,x,C)){
//                cout<<"[get]: "<<get(o,x,C).F<<" "<<get(o,x,C).S<<endl;
//                cout<<"[get]: "<<get(o+1,x,C).F<<" "<<get(o+1,x,C).S<<endl;
                o++;
            }

            auto [ans0, cnt0]=get(o,x,C);
//            cout<<"[o]: "<<o<<" "<<dq.size()<<" "<<ans0<<" "<<cnt0<<endl;
            ans+=ans0;
            cnt+=cnt0;
            ll s=v[i-1].F;
//            if(i>1 && v[i-2].S>s)s=v[i-2].S;
            dp[i]=min(dp[i], {dp[i-1].F+(r-s)*(r-s)+C, dp[i-1].S+1});
//            cout<<"[i, ans, cnt, C]: "<<i<<" "<<ans<<" "<<cnt<<" "<<C<<endl;

            if(i==n)continue;

            ll l=v[i].F;
            add(-2*l, ans + l*l - max((ll)0, r-l)*max((ll)0, r-l), cnt);

//    dp + (r1-l)^2 - (r2-l)^2
//    dp + r1*r1 + l*l - 2*r1*l - (r2-l)^2
//    (-2*l) * r1 + (dp - l*l + (r-l)^2)

        }
//        for (auto [x, y]:dp){
//            cout<<"[dp]: "<<x<<" "<<y<<endl;
//        }
}


ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    ll Ans=0;
    vector<pll> v, V(n);

    for (int i=0; i<n; i++){
        if(c[i]<r[i])swap(r[i], c[i]);
        V[i]={r[i], -c[i]};
    }

    sort(all(V));
    ll rr=-1;
    for (auto [l,r]:V){
        r*=-1;
//        cout<<r<<endl;
        if(r>rr)v.pb({l,r+1});
        rr=max(r, rr);
    }
    V.clear();
    n=v.size();

//    for (auto [l,r]:v){
//        cout<<"[l, r]: "<<l<<" "<<r<<endl;
//    }

    ll L=0, R=1ll*m*m;
//    L=49, R=49;
    while(L<=R){
        ll C=(L+R)>>1;
        vector<pll> dp(n+1);
        calc_dp(n, v, dp, C);
//        cout<<"[C,K]: "<<C<<" "<<dp[n].S<<endl;
        if(dp[n].S>k){
            L=C+1;
        }else{
            Ans=dp[n].F;
//            cout<<"[C, Ans]: "<<C<<" "<<Ans<<endl;
            R=C-1;
        }
        dq.clear();
        o=0;
    }

//        cout<<Ans<<" "<<Ans-L*k<<" "<<R<<" "<<L<<endl;
    return Ans-L*k;
}

Compilation message (stderr)

aliens.cpp: In function 'bool check(long long int, long long int)':
aliens.cpp:18:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     auto [k0,b0]=dq[e-1].F;
      |          ^
aliens.cpp:19:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     auto [k1,b1]=dq[e-2].F;
      |          ^
aliens.cpp: In function 'std::pair<long long int, long long int> get(int, long long int, long long int)':
aliens.cpp:40:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(i==dq.size()){
      |        ~^~~~~~~~~~~
aliens.cpp:43:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     auto [k,b]=dq[i].F;
      |          ^
aliens.cpp: In function 'void calc_dp(int, std::vector<std::pair<long long int, long long int> >, std::vector<std::pair<long long int, long long int> >&, long long int)':
aliens.cpp:52:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |             auto &[ans, cnt]=dp[i];
      |                   ^
aliens.cpp:65:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |             auto [ans0, cnt0]=get(o,x,C);
      |                  ^
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:101:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  101 |     for (auto [l,r]:V){
      |               ^

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40