제출 #224925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224925		jhnah917	Aliens (IOI16_aliens)	C++14	25 / 100	21 ms	9344 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> p;
 
int n, m, k;
ll dp[555][101010];
p a[101010];
vector<p> v;
 
struct CHT{
    struct Line{
        ll a, b, c;
        Line(){ a = b = c = 0; }
        Line(ll a, ll b, ll c) : a(a), b(b), c(c) {}
        ll f(ll x){ return a*x+b; }
    };
    vector<Line> v; int pv;
    void init(){ v.clear(); pv = 0; }
    int chk(const Line &a, const Line &b, const Line &c){
        return (a.b - b.b) * (c.a - b.a) >= (b.b - c.b) * (b.a - a.a);
    }
    void update(Line l){
        if(v.size() && v.back().a == l.a){ v.back() = l; return; }
        while(v.size() >= 2 && chk(v[v.size()-2], v.back(), l)) v.pop_back();
        v.push_back(l);
        if(pv >= v.size()) pv = v.size() - 1;
    }
    p query(ll x){
        while(pv+1 < v.size() && v[pv].f(x) >= v[pv+1].f(x)) pv++;
        return {v[pv].f(x), v[pv].c};
    }
} cht;
 
void init(int N, int M, int K, const vector<int> &R, const vector<int> &C){
    m = M, k = K; v.clear();
    for(int i=0; i<N; i++) v.emplace_back(max(R[i], C[i]) + 1, min(R[i], C[i]));
    sort(all(v));
    for(int i=0; i<N; i++){
        while(n && a[n].y >= v[i].y) n--;
        a[++n] = v[i];
    }
    for(int i=1; i<=n; i++) dp[1][i] = (a[i].x - a[1].y) * (a[i].x - a[1].y);
}
 
ll take_photos(int N, int M, int K, vector<int> R, vector<int> C){
    init(N, M, K, R, C);
    int q = min(n, k);
    if(q > 500) return -1;
 
    for(int i=2; i<=q; i++){
        cht.init(); cht.update(CHT::Line(-2 * a[1].y, a[1].y * a[1].y, 0));
        for(int j=1; j<=n; j++){
            dp[i][j] = cht.query(a[j].x).x + a[j].x * a[j].x;
            ll ta = a[j+1].y, tb = max(0LL, a[j].x - a[j+1].y);
            ll aa = -2 * a[j+1].y;
            ll bb = dp[i-1][j] + ta*ta - tb*tb;
            cht.update(CHT::Line(aa, bb, i));
        }
    }
    // for(int i=1; i<=q; i++){
    //     for(int j=1; j<=n; j++) cout << dp[i][j] << " ";
    //     cout << "\n";
    // }
    return dp[q][n];
}
 
// g++ -O2 -std=c++11 -static -o main grader.cpp aliens.cpp aliens.h

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In member function 'void CHT::update(CHT::Line)':
aliens.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pv >= v.size()) pv = v.size() - 1;
            ~~~^~~~~~~~~~~
aliens.cpp: In member function 'p CHT::query(ll)':
aliens.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pv+1 < v.size() && v[pv].f(x) >= v[pv+1].f(x)) pv++;
               ~~~~~^~~~~~~~~~

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