#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;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000004, expected = 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000001, expected = 1 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000004, expected = 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000004, expected = 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000004, expected = 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Wrong answer: output = 1000000000000000004, expected = 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
