Submission #963371

#	Time	Username	Problem	Language	Result	Execution time	Memory
963371		hyakup	Aliens (IOI16_aliens)	C++17	0 / 100	26 ms	64960 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const int maxn = 510;
const int maxk = 510;
const int maxm = 1e3 + 10;
const ll inf = 1e17 + 10;

ll dp[maxn][maxk];

struct Point{
  int x, y; Point( int x, int y ) : x(x), y(y) {}
  bool operator < ( Point p ){ return (( x == p.x ) ? y < p.y : x > p.x ); }
}; vector<Point> point, pareto;

struct Line{
  ll a, b; Line( ll a = maxn, ll b = maxn ): a(a), b(b) {}
  ll get_val( ll x ){ return a*x + b; }
};
class lichao_tree{
public:
  void refresh( int pos, int ini, int fim ){
    if( lazy[pos].a == maxn && lazy[pos].b == maxn ) return;
    Line x = seg[pos] = lazy[pos]; lazy[pos] = Line(maxn, maxn);
    if( ini == fim ) return;
    int l = 2*pos, r = 2*pos + 1;
    lazy[l] = lazy[r] = x;
  }
  void add( int pos, int ini, int fim, Line nova ){
    refresh(pos, ini, fim);
    if( ini == fim ){ if( nova.get_val(ini) < seg[pos].get_val(ini) ) seg[pos] = nova; return; }
    int mid = ( ini + fim )/2, l = 2*pos, r = 2*pos + 1;
    if( seg[pos].get_val(mid) > nova.get_val(mid) ){
      lazy[pos] = nova; refresh(pos, ini, fim);
      swap( seg[pos], nova );
    }
    if( seg[pos].get_val(ini) > nova.get_val(ini) ) add( l, ini, mid, nova );
    else add( r, mid + 1, fim, nova );
  }
  ll query( int pos, int ini, int fim, int id ){
    if( ini == fim ) return seg[pos].get_val(id);
    int mid = ( ini + fim )/2, l = 2*pos, r = 2*pos + 1;
    if( id <= mid ) return min( seg[pos].get_val(id), query( l, ini, mid, id ) );
    else return min( seg[pos].get_val(id), query( r, mid + 1, fim, id ) );
  }

  void insere( int i, int k ){
    Point A = pareto[i];
    Line nova( -2*A.x, A.x*A.x + dp[i - 1][k - 1] );
    // cout << "a " << nova.a << " b " << nova.b << endl;
    add( 1, 0, maxm, nova );
  }
  lichao_tree(){ seg = lazy = vector<Line>(4*maxm); }
private:
  vector<Line> seg, lazy;
} tree[maxk];


void build( vector<int>& r, vector<int>& c ){
  for( int i = 0; i < r.size(); i++ ){
    if( c[i] > r[i] ) swap( r[i], c[i] );
    point.push_back( Point( c[i], r[i] ) );
  }
  sort( point.begin(), point.end() );
  set<pair<int, int>> s;
  for( auto cur : point ){
    // bug(cur.x);
    // bug(cur.y);
    s.insert({ cur.y, cur.x });
    while( *s.begin() != make_pair( cur.y, cur.x ) ) s.erase(s.begin());
  }
  pareto.push_back(Point(0, 0));
  for( auto [y, x] : s ){
    // bug(x);
    // bug(y);
    pareto.push_back(Point(x - 1, y));
  }
}

ll solve( int n, int k ){
  ll resp = inf;
  for( int i = 0; i < pareto.size(); i++ ) for( int j = 0; j < k; j++ ) dp[i][j] = inf;
  dp[0][0] = 0;
  for( int i = 1; i < pareto.size(); i++ ){
    // bug(i);
    // cout << "X " << pareto[i].x << " Y " << pareto[i].y << endl;
    for( int j = 1; j <= k; j++ ){
      // bug(j);
      tree[j - 1].insere( i, j );
      dp[i][j] = pareto[i].y*pareto[i].y + tree[j - 1].query( 1, 0, maxm, pareto[i].y );
      // bug(dp[i][j]);
      if( i == pareto.size() - 1 ) resp = min( resp, dp[i][j] );
    }
  }
  return resp;
}

ll take_photos( int n, int m, int k, vector<int> r, vector<int> c) {
    build( r, c );
    return solve( n, k );
}

// int main(){
//   int n, m, k; cin >> n >> m >> k;
//   vector<int> r(n), c(n); for( int i = 0; i < n; i++ ) cin >> r[i] >> c[i];
//   cout << take_photos( n, m, k, r, c );
// }

Compilation message (stderr)

aliens.cpp: In function 'void build(std::vector<int>&, std::vector<int>&)':
aliens.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for( int i = 0; i < r.size(); i++ ){
      |                   ~~^~~~~~~~~~
aliens.cpp: In function 'long long int solve(int, int)':
aliens.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for( int i = 0; i < pareto.size(); i++ ) for( int j = 0; j < k; j++ ) dp[i][j] = inf;
      |                   ~~^~~~~~~~~~~~~~~
aliens.cpp:87:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for( int i = 1; i < pareto.size(); i++ ){
      |                   ~~^~~~~~~~~~~~~~~
aliens.cpp:95:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |       if( i == pareto.size() - 1 ) resp = min( resp, dp[i][j] );
      |           ~~^~~~~~~~~~~~~~~~~~~~

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