Submission #1082671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082671		hqminhuwu	Aliens (IOI16_aliens)	C++14	100 / 100	163 ms	13608 KiB

aliens

//#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
 
#define forr(_a,_b,_c) for(int _a = (_b); _a <= int (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> int (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < int (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
 
template<class X, class Y>
    bool minz(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } return false;
    }
template<class X, class Y>
    bool maxz(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } return false;
    }
 
const int N = 1e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
 
struct line {
    ll m, c;
    ll eval (ll x) { return m * x + c; }
    ld its (line l) { return (ld) (c - l.c) / (l.m - m); }
};
 
ll sqr (ll x){
    return x * x;
}
 
ll dp[N], cnt[N];
vector <pll> v;
map <ll, ll> z;
 
void calc (ll x){
    deque <line> dq;
    deque <int> dqcnt;
    dq.push_front({-2 * v[0].st, x + 1 + sqr(v[0].st) - 2 * v[0].st});
    dqcnt.push_front(0);
    
    forf (i, 0, v.size()){
 
        while (dq.size() >= 2 && dq.back().eval(v[i].nd) > dq[dq.size() - 2].eval(v[i].nd)){
            dq.pop_back();
            dqcnt.pop_back();
        }
    
        dp[i] = dq.back().eval(v[i].nd) + sqr(v[i].nd) + 2 * v[i].nd;
        cnt[i] = dqcnt.back() + 1;
 
        if (i == v.size() - 1) return;
        
        line cur = {-2 * v[i + 1].st, dp[i] + x + 1 - sqr(max(0ll, v[i].nd - v[i + 1].st + 1)) 
            + sqr(v[i + 1].st) - 2 * v[i + 1].st};
 
        while (dq.size() >= 2 && cur.its(dq[0]) <= dq[0].its(dq[1])){
            dq.pop_front();
        	dqcnt.pop_front();
        }
        dqcnt.push_front(cnt[i]);
        dq.push_front(cur);
    }
}
 
ll take_photos (int n, int m, int k, vector <int> r, vector <int> c){
    forf (i, 0, n){
        if (r[i] > c[i]) swap(r[i], c[i]);
        maxz(z[r[i]], c[i]);
    }
 
    ll mx = -1;
    for (pll t : z){
        if (t.nd > mx){
            v.pb(t);
            mx = t.nd;
        }
    }
    
    ll l = 0, h = 1ll * m * m;
    n = v.size() - 1;
 
    // for (pii t : v)
    //     cout << t.st << " " << t.nd << "\n";
 
    while (l < h){
        ll mid = (l + h) >> 1;
        calc(mid);
        //cout << mid << " " << cnt[n] << endl;
        if (cnt[n] > k)
            l = mid + 1;
        else h = mid;
    } 
 
    calc(l);
 
    //cout << dp[n] << " " << cnt[n] << " " << l << endl;; 
    
    return dp[n] - k * l;
}
 
 

Compilation message (stderr)

aliens.cpp: In function 'void calc(ll)':
aliens.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if (i == v.size() - 1) return;
      |             ~~^~~~~~~~~~~~~~~

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