제출 #239204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239204		nicolaalexandra	Aliens (IOI16_aliens)	C++14	0 / 100	8 ms	512 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
#define DIMN 100010
#define DIMM 1000010
using namespace std;

int n,k,m,i,j,x,y;
vector <int> r,c;

long long dp[DIMN][2];
pair <int, int> v[DIMN];

struct dreapta{
    long long a,b;
} aint[DIMM*4];

long long f (long long a, long long b, int x){
    return a*x + b;
}

void add (int nod, int st, int dr, long long a, long long b){
    if (st == dr){
        if (f(a,b,st) < f(aint[nod].a,aint[nod].b,st))
            aint[nod] = {a,b};
        return;
    }
    int mid = (st+dr)>>1;
    int ok_mid = 0, ok_dr = 0;
    if (f(a,b,mid) <= f(aint[nod].a,aint[nod].b,mid))
        ok_mid = 1;
    if (f(a,b,dr) <= f(aint[nod].a,aint[nod].b,dr))
        ok_dr = 1;

    if (!ok_mid && !ok_dr)
        add (nod<<1,st,mid,a,b);
    else {
        if (!ok_mid && ok_dr)
            add ((nod<<1)|1,mid+1,dr,a,b);
        else {
            swap (aint[nod].a,a);
            swap (aint[nod].b,b);

            if (ok_dr)
                add (nod<<1,st,mid,a,b);
            else add ((nod<<1)|1,mid+1,dr,a,b);
        }}}

long long query (int nod, int st, int dr, int x){
    if (st == dr)
        return f(aint[nod].a,aint[nod].b,x);
    int mid = (st+dr)>>1;
    long long sol = 0;
    if (x <= mid)
        sol = query (nod<<1,st,mid,x);
    else sol = query ((nod<<1)|1,mid+1,dr,x);

    return max (sol,f(aint[nod].a,aint[nod].b,x));
}

long long patrat (long long x){
    return x*x;
}

long long take_photos (int N, int m, int K, std::vector <int> R, std::vector <int> C){
    n = N, k = K;
    for (i=0;i<n;i++)
        v[i+1] = make_pair(r[i],c[i]);

    sort (v+1,v+n+1);

    int el = 1;
    for (i=2;i<=n;i++)
        if (v[i] != v[i-1])
            v[++el] = v[i];

    n = el;

    /// dp[i][j] - costul minim sa parcurg primele i puncte si sa am j subsecvente

    for (i=1;i<=n;i++)
        dp[i][1] = patrat (v[i].first - v[1].second + 1);

    int t = 0;

    for (j=2;j<=k;j++){

        for (i=1;i<=4*m;i++)
            aint[i] = {0,0};

        for (i=j;i<=n;i++){
            add (1,1,n,-2*v[i].second,dp[i-1][1-t] + patrat(v[i].second));

            dp[i][t] = patrat(v[i].first + 1) + query (1,1,n,v[i].first+1);
        }

        t = 1-t;
    }

    return dp[n][1-t];

}

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