Submission #1022083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022083		vjudge1	Aliens (IOI16_aliens)	C++17	4 / 100	15 ms	24156 KiB

aliens

#include <bits/stdc++.h>
#define ent '\n'

typedef long long ll;
using namespace std;
const int maxn = 1e6+12;

vector<int> g[maxn];
ll dp[maxn][101];
int L[maxn];
int R[maxn];

struct line{
    ll k, b;
    line(){
        k = 0, b = 0;
    }
    line(int x, int y){
        k = x, b = y;
    }
    ll get(ll x){
        return k * x + b;
    }
    double inter(line x){
        return (double)(b - x.b) / (double)(x.k - k);
    }
};

struct CHT{
    vector<line> ord;
    int ptr = 0;

    CHT(){
        ord.clear();
        ptr = 0;
    }

    void add(line x){
        while(ord.size() && ord.back().k == x.k){
            if(ord.back().b < x.b){
                return;
            }
            ord.pop_back();
        }
        while(ord.size() > 1 && ord.back().inter(ord[ord.size()-2]) > x.inter(ord[ord.size()-2])){
            ord.pop_back();
        }
        ord.push_back(x);
    }

    ll get(ll x){
        while(ptr >= ord.size() || ptr > 0 && ord[ptr].get(x) > ord[ptr-1].get(x)){
            ptr--;
        }
        while(ptr < 0 || ptr + 1 < ord.size() && ord[ptr].get(x) > ord[ptr+1].get(x)){
            ptr++;
        }
        return ord[ptr].get(x);
    }
} cht[101];

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    for(int i=1;i<=m;i++){
        L[i] = 1e9;
    }
    m = 0;
    for(int i=0;i<n;i++){
        if(r[i] < c[i]){
            swap(r[i], c[i]);
        }
        r[i]++, c[i]++;
        L[r[i]] = min(L[r[i]], c[i]);
        R[c[i]] = max(R[c[i]], r[i]);
        m = max(m, r[i]);
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<=k;j++){
            dp[i][j] = 1e12;
        }
    }
    for(int i=0;i<=k;i++){
        cht[i].add({0, 0});
    }
    for(int i=1;i<=m;i++){
        R[i] = max(R[i], R[i-1]);
        for(int t=1;t<=k;t++){
            dp[i][t] = cht[t-1].get(i) + i * i;
        }
        for(int j=i-1;j>=0;j--){
            for(int t=1;t<=k;t++){
                int l = R[j];
                ll val = dp[l][t-1] + (i - j) * (i - j);
                if(l >= i) continue;
                if(l > j) val -= (l - j) * (l - j);
                dp[i][t] = min(dp[i][t], val);
            }
        }
        g[max(i, R[i])].push_back(i);
        for(int j:g[i]){
            for(int t=0;t<=k;t++){
                cht[t].add(line(-2 * j, (R[j] - j) * (R[j] - j) + j * j + dp[R[j]][t]));
            }
        }
    }
    return dp[m][k];
}

Compilation message (stderr)

aliens.cpp: In member function 'll CHT::get(ll)':
aliens.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         while(ptr >= ord.size() || ptr > 0 && ord[ptr].get(x) > ord[ptr-1].get(x)){
      |               ~~~~^~~~~~~~~~~~~
aliens.cpp:52:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   52 |         while(ptr >= ord.size() || ptr > 0 && ord[ptr].get(x) > ord[ptr-1].get(x)){
      |                                    ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aliens.cpp:55:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while(ptr < 0 || ptr + 1 < ord.size() && ord[ptr].get(x) > ord[ptr+1].get(x)){
      |                          ~~~~~~~~^~~~~~~~~~~~
aliens.cpp:55:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |         while(ptr < 0 || ptr + 1 < ord.size() && ord[ptr].get(x) > ord[ptr+1].get(x)){
      |                          ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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