제출 #158999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158999		crackersamdjam	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	380 KiB

aliens

#define SUBMIT
#ifdef SUBMIT
#include "aliens.h"
#endif
#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

#define sq(x) (x)*(x)
#define peek(x) std::cout << #x << ' ' << x << std::endl

using namespace std;
using ll = long long;
using ld = long double;
using pii =  pair<int, int>;
const int MM = 1e5+5;
const ld eps = 1e-12;

int n, q[MM], cnt[MM];
ld dp[MM];
vector<pii> a, b;
set<int> st;

bool cmp(const pii &x, const pii &y){
    if(x.first != y.first)
        return x.first < y.first;
    return x.second > y.second;
}

ld eval(int l, int i){
    //printf("eval %d %d %lld %lld\n", l, i, sq((ll)a[i].first - a[l+1].second + 1), -sq((ll)max(0, a[l].first - a[l+1].second + 1)));
    //return dp[l] + sq((ll)a[i].first - a[l+1].second + 1) - sq((ll)max(0, a[l].first - a[l+1].second + 1));
    //printf("eval %d %d %lld %lld\n", l, i, sq((ll)a[i].second - a[l+1].first + 1), -sq((ll)max(0, a[l].second - a[l+1].first + 1)));
    return dp[l] + sq((ll)a[i].second - a[l+1].first + 1) - sq((ll)max(0, a[l].second - a[l+1].first + 1));
    //dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2
}

int inter(int i, int f, int s){
    int l = i, m, r = n;
    while(l <= r){
        m = (l+r)/2;
        if(eval(f, m) < eval(s, m))
            l = m+1;
        else
            r = m-1;
    }
    //printf("inter %d %d = %d\n", f, s, l);
    //find first when f gives higher (or equal)
    //will never use f again
    return l;
}

void run(ld cost, int K){
    //printf("run %Lf\n", cost);
    int l = 0, r = 0; q[0] = 0;
    for(int i = 1; i <= n; i++){
        
        //while(r-l >= 1 && i*(dp[q[l]] - dp[q[l+1]]) <=  q[l] - q[l+1])
          //  l++;
          
        //printf("compare %d, %Lf %Lf\n", r-l, eval(q[l], i), eval(q[l+1], i));
        while(r-l >= 1 && (eval(q[l], i) >= eval(q[l+1], i))){
            l++;
        }
        
        //peek(l);
        dp[i] = eval(q[l], i) + cost;
        cnt[i] = cnt[q[l]] + 1;
        //printf("%d %Lf %d\n", i, dp[i], cnt[i]);
        
        while(r-l >= 1 && inter(i, q[r-1], q[r]) >= inter(i, q[r], i)){
            r--;
        }
        
        q[++r] = i;
    }
    //printf("res %Lf\n", dp[n]-cost*K);
}

long long take_photos(int Ln, int M, int K, vector<int> R, vector<int> C){

    n = Ln;
    
    for(int i = 0; i < n; i++){
        if(R[i] < C[i])
            swap(R[i], C[i]);
        a.push_back({C[i], R[i]});
        //flip
    }
    
    sort(a.begin(), a.end(), cmp);
    
    /*
    puts("a");
    for(auto i: a)
        print(i.first, i.second);
    */
    //add filter to remove points with points top-right of it
    
    for(int i = 0; i < a.size(); i++){
        //print(a[i].first, a[i].second, -1);
        if(st.lower_bound(a[i].second) == st.end())
            b.push_back(a[i]);
        st.insert(a[i].second);
    }
    
    a = b;
    /*
    puts("b");
    for(auto i: a)
        print(i.first, i.second);
    puts("ok");
    */
    n = a.size();
    
    a.insert(a.begin(), {-1, -1});
    //indexing
    
    ld l = 0, m, r = 20;
    while(r-l >= eps){
        m = (l+r)/2;
        run(m, K);
        if(cnt[n] >= K)
            l = m;
        else
            r = m;
    }
    
    run(r, K);
    
    //cout << dp[n] << ' ' << r*K << ' ' << dp[n]-r*K << ' ' << round(dp[n]-r*K) << '\n';

    return round(dp[n] - r*K);
}

#ifndef ONLINE_JUDGE
/*
int main(){
    
    int i1, i2, i3;
    scan(i1, i2, i3);
    int a1[i1], a2[i1];
    for(int i = 0; i < i1; i++)
        scan(a1[i], a2[i]);
    print(take_photos(i1, i2, i3, a1, a2));
    
    int a1[] = {0, 4, 4, 4, 4}, a2[] = {3, 4, 6, 5, 6},
    a3[] = {1, 4}, a4[] = {4, 1};
    print(take_photos(5, 7, 2, a1, a2));
    //print(take_photos(2, 6, 2, a3, a4));
    
    return 0;
}
*/

#endif

/*
 * n^2 k sol
 * dp[k][i] = min{dp[k-1][j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2}
 * (x is down, y is right)
 *(max(0, x[j] - y[j+1]))^2   --may not need to subtract
 * 
 * dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2 <= dp[k] + (x[i] - y[k+1])^2 - (x[k] - y[k+1])^2  ;  j < k
 * dp[j] + (x[i] - y[j+1])^2 - (x[j] - y[j+1])^2 <= dp[k] + (x[i] - y[k+1])^2 - (x[k] - y[k+1])^2
 *
 * just bs :monkey:
 */

/*
 * akvizna:
 dp[i] = dp[j] + (i-j)/i + c
 dp[j] + (i-j)/i <= dp[k] + (i-k)/i; j < k
 dp[j]*i + (i-j) <= dp[k]*i + (i-k)
 dp[j]*i - dp[k]*i <= j-k
 i*(dp[j] - dp[k]) <= j-k
 // can not divide the inequality bc. dp[j]-dp[k] may be neg., but intersect works because looking for equality
 */

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++){
                    ~~^~~~~~~~~~

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