Submission #1246312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246312		catgirl	Aliens (IOI16_aliens)	C++20	25 / 100	2095 ms	24100 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifndef ONLINE_JUDGE
#define w(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define MAXN (long long int) (1e5 + 5)
#else
#define w(...)
#define MAXN (long long int) (1e5 + 5)
#endif

// DEFINES/MACROS
#define pb push_back
#define st first 
#define nd second 
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

// TYPEDEFS
typedef long long int ll;
typedef vector<ll> vi;
typedef set<ll> si;
typedef pair<ll, ll> pll;

template<typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxheap = priority_queue<T>;
template<typename T>
using vec = vector<T>;

// CONSTS

const ll inf = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const string yes = "YES";
const string no = "NO";
const string yesn = "YES\n";
const string non = "NO\n";
const string nl = "\n";

struct Line {
	mutable ll k, m, p, taken;
	bool operator<(const Line& o) const { 
        if (k == o.k) return taken > o.taken;
        return k < o.k; 
    }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> { // -(x - i)^2
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m, ll t) { // INVERTED SIGNS, WILL FIND MINIMUM
		auto z = insert({-k, -m, 0, t}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	pll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return {-l.k * x - l.m, l.taken};
	}
};

ll take_photos(int n, int m, int k, vec<int> r, vec<int> c) { // 
    vec<pll> intervals(n);
    for (ll i = 0; i < n; i++) {
        auto [x, y] = minmax(r[i], c[i]);
        intervals[i] = {x, y};
    }

    sort(all(intervals), [&](const pll& a, const pll& b) {
        if (a.st != b.st) return a.st < b.st;
        return a.nd > b.nd;
    });

    
    vi jmps(m+1);
    ll rightendpoint = -1;
    for (auto [l, r] : intervals) {
        if (r <= rightendpoint) continue;
        rightendpoint = r;
        jmps[l] = r+1;
    }
    
    auto get = [&](ll lambda)->ll {
        vec<pll> dp(m+1, {inf, 0});
        LineContainer CHT; // gets minimum

        ll maxr = 0;
        dp[0] = {0, 0};
        for (ll i = 0; i < m; i++) {
            ll savable = max(maxr - i, 0ll);
            ll saved = savable*savable;
            CHT.add(-2*i, i*i + dp[i].st - saved, -dp[i].nd);
            if (jmps[i]) {
                ll r = jmps[i];
                pll best = CHT.query(r);

                maxr = r;
                ll cost = best.st + r*r + lambda;
                ll taken = best.nd + 1;
                dp[i+1] = min(dp[i+1], {cost, -taken});
            }
            else {
                dp[i+1] = min(dp[i+1], dp[i]);
            }
        }

        if (-dp[m].nd <= k) { // is no of segments valid?
            return dp[m].st - lambda * (k);
        }
        else return -inf;
    };
    
    ll lo = 0; 
    ll hi = 1ll*m*m + 1;
    ll ans = inf;
    while (lo <= hi) {
        ll lamb = (lo+hi)/2;
        ll res;
        if ((res = get(lamb)) > -inf) {
            ans = res;
            hi = lamb - 1;
        }
        else lo = lamb + 1;
    }

    return ans;


}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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