제출 #1225464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225464		Hamed_Ghaffari	Aliens (IOI16_aliens)	C++20	100 / 100	179 ms	9744 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

#define X first
#define Y second
#define mid ((l+r)>>1)

inline ll fdiv(ll a, ll b) {
    bool sgn = 0;
    if(a<0) {
        sgn ^= 1;
        a = -a;
    }
    if(b<0) {
        sgn ^= 1;
        b = -b;
    }
    return sgn ? - (a+b-1)/b : a/b;
}

inline ll isect(pll f, pll g) {
    return fdiv(f.Y-g.Y, g.X-f.X);
}

inline ll eval(pll f, ll x) {
    return f.X*x + f.Y;
}

struct cht : vector<pll> {
    vector<ll> vec;
    vector<int> id;
    inline void add(pll ln, int id_) {
        while(!empty()) {
            vec.back() = isect(back(), ln);
            if(vec.size()==1 || vec.back()>vec[vec.size()-2]) break;
            vec.pop_back();
            pop_back();
            id.pop_back();
        }
        vec.push_back(1e9);
        push_back(ln);
        id.push_back(id_);
    }
    inline pll get(ll x) {
        int pos = lower_bound(vec.begin(), vec.end(), x)-vec.begin();
        return {eval((*this)[pos], x), id[pos]};
    }
};

const int MXN = 1e5+5;

int n, L[MXN], R[MXN];
ll dp[MXN];
int cnt[MXN];

inline void add(cht &ds, int j) {
    ll tmp = max(0, R[j]-L[j+1]+1);
    ds.add({-2*L[j+1], dp[j] + 1ll*L[j+1]*L[j+1] - tmp*tmp}, j);
}

ll take_photos(int nn, int m, int k, vector<int> LL, vector<int> RR) {
    for(int i=0; i<nn; i++)
        if(LL[i]>RR[i])
            swap(LL[i], RR[i]);
    vector<int> ord(nn);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return pll(LL[i], -RR[i]) < pll(LL[j], -RR[j]);
    });
    L[0] = R[0] = -1;
    for(int i=0; i<nn; i++)
        if(RR[ord[i]]>R[n]) {
            L[++n] = LL[ord[i]];
            R[n] = RR[ord[i]];
        }
    auto alien = [&](ll cost) -> pll {
        cht ds;
        add(ds, 0);
        for(int i=1; i<=n; i++) {
            pll d = ds.get(R[i]+1);
            dp[i] = cost + 1ll*(R[i]+1)*(R[i]+1) + d.X;
            cnt[i] = cnt[d.Y]+1;
            if(i<n) add(ds, i);
        }
        return {dp[n], cnt[n]};
    };
    ll l=-1, r=1ll*m*m+1;
    while(r-l>1)
        (alien(mid).Y<=k ? r : l) = mid;
    pll ans = alien(r);
    return ans.X - k*r;
}

컴파일 시 표준 에러 (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: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40