Submission #108604

#	Time	Username	Problem	Language	Result	Execution time	Memory
108604		rajarshi_basu	Aliens (IOI16_aliens)	C++14	0 / 100	2 ms	384 KiB

aliens

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
//#include <string>
//#include <map>
//#include <complex>
//#include <chrono>
//#include <random>
//#include <stack>
//#include <set>
//#include <fstream>
 
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a; i <= b ; i++)
#define ss second
#define ff first
#define ll long long int
#define ii pair<ll,ll>
#define il pair<int,ll>
#define li pair<ll,int>
#define x ff
#define y ss
#define lii pair<ll,pair<int,int> > 
#define piil pair<int ,pair<int,int> > 
#define iii pair<pair<int,int>,int> 
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define mp make_pair
 
#include "aliens.h"
 
using namespace std;
 
const ll INF = 1e18;
 
vector<ii> all;
 
vector<ii> reduceList(vector<ii> v){
	sort(v.begin(), v.end());
	vector<ii> res;
	ll mx = 0;
	for(auto e:v){
 
		if(res.empty())res.pb(e);
		else if(res.back().ff < e.ff){
			if(e.ss > mx)res.pb(e);
		}else{
			res.back() = e;
		}
		mx = max(mx,e.ss);
	}
	return res;
} 
vector<ii> createRanges(vi r,vi c,int n){
	vector<ii> all;
	FOR(i,n)all.pb({min(r[i],c[i]),max(r[i],c[i])});
	return all;
}
 
ll C1[100*1000+1];
void prec(){
	C1[0] = 0;	
	FORE(i,1,(int)all.size()-1){
		C1[i] = max((ll)0,all[i-1].ss - all[i].ff+1);
		C1[i] *= C1[i];
	}
}
 
ll cost(int t,int i){
    i--;
    //cout << "afsf " << i << " " << all.size() <<  endl;
    ll t1 = all[i].ss - all[t].ff + 1; t1*=t1;
    ll t2 = C1[t];
    //cout << t1 << " " << t2 << endl;
    //cout << t1-t2 << endl;
    return t1 - t2;
}
 

class SqrtSegtree{
    deque<pair<pll,int> > cht;
    inline ll eval(pll p1,ll x){
        return p1.ff*x+p1.ss;
    }
    inline void update(pair<pll,int> e){
        cht.push_back(e);
    }
    public : 
    inline void addLine(ll m,ll c,int id){
        update({{m,c},id});
    }

    inline li query(ll x){
        li best = {INF,0};
        for(auto e:cht){
            if(best.ff < eval(e.ff,x)){
                best.ff = eval(e.ff,x);
                best.ss = e.ss;
            }
        } 
        return best;//binsrch(x);
    }
    inline void init(){
       // buffer.clear();
        cht.clear();
    }
};
 
li dp[100*1000+1];
//int opt[2][100*1000+1];
ll E[100*1000+1];
//int opt[50*1000+1][2];
//Segtree ds[50*1000+1];
//SqrtSegtree ds;
li computeDp(ll CC){
    int n = all.size();
	vector<ll> add;
    FOR(i,n){
		add.pb(all[i].ss*all[i].ss + 1 + 2*all[i].ss);
	}
    
    FOR(i,n)E[i] = all[i].ff*all[i].ff - 2*all[i].ff;
    SqrtSegtree ds;
    dp[0] = {0,0};
    for(int i = 1;i <= n;i++){
        ds.addLine((-2*all[i-1].ff),(dp[i-1].ff - C1[i-1] + E[i-1]) , dp[i-1].ss);
        li mn = ds.query(all[i-1].ss);
        // cout << "VAL : " << i << " " << mn.ff << endl;
        dp[i] = {mn.ff + CC + add[i-1],mn.ss+1};
    }

    return dp[n];
}

int check(ll C,int k){
    li v1 = computeDp(C);
    return v1.ss;
}

ll binsrch(int k){
    for(int i = 0;;i++){
        auto v = computeDp(i);
        if(v.ss <= k){
            if(v.ss != k)return (((ll)v.ss)*10000 + k)*1000000000;
            return v.ff - v.ss*i;
        }
    }
}
ll take_photos(int n,int m,int k,vi r,vi c){
	all = reduceList(createRanges(r,c,n));
	prec();
    k = min(k,(int)all.size());
    ll ans = binsrch(k);
    return ans;
}
 
 
/*
int main(){
	//int a[2] = {2,4,4,4,4};
	//int b[2] = {3,5,6,5,6};
	vi a;
	vi b;
	a.pb(1000000);a.pb(0);a.pb(666);a.pb(10000-3);a.pb(100000-4);//a.pb(4);a.pb(4);a.pb(4);
	b.pb(1000000);b.pb(0);b.pb(666);b.pb(10000-3);b.pb(100000-4);//a.pb(4);a.pb(4);a.pb(4);
	cout << take_photos(5,7,1,a,b) << endl;
	return 0;
}
*/

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