Hard Disk Drives
Problem Statement :
There are n pairs of hard disk drives (HDDs) in a cluster. Each HDD is located at an integer coordinate on an infinite straight line, and each pair consists of one primary HDD and one backup HDD. Next, you want to place k computers at integer coordinates on the same infinite straight line. Each pair of HDDs must then be connected to a single computer via wires, but a computer can have any number (even zero) of HDDs connected to it. The length of a wire connecting a single HDD to a computer is the absolute value of the distance between their respective coordinates on the infinite line. We consider the total length of wire used to connect all the HDDs to computers to be the sum of the lengths of all the wires used to connect HDDs to computers. Note that both the primary and secondary HDDs in a pair must connect to the same computer. Given the locations of n pairs (i.e., primary and backup) of HDDs and the value of k, place all k computers in such a way that the total length of wire needed to connect each pair of HDDs to computers is minimal. Then print the total length on a new line. Input Format The first line contains two space-separated integers denoting the respective values of n (the number of pairs of HDDs) and k (the number of computers). Each line i of the n subsequent lines contains two space-separated integers describing the respective values of ai (coordinate of the primary HDD) and bi (coordinate of the backup HDD) for a pair of HDDs. Constraints 2 <= k <= n <= 10^5 4 <= k*n <= 10^5 -10^9 <= ai,bi <= 10^9 Output Format Print a single integer denoting the minimum total length of wire needed to connect all the pairs of HDDs to computers.
Solution :
Solution in C :
In C++ :
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long sa, sb;
int sc;
node()
{
sa=sb=sc=0;
}
node(long long a, long long b, int c)
{
sa=a, sb=b, sc=c;
}
node& operator+= (const node& other)
{
sa+=other.sa;
sb+=other.sb;
sc+=other.sc;
return *this;
}
node& operator-= (const node& other)
{
sa-=other.sa;
sb-=other.sb;
sc-=other.sc;
return *this;
}
bool operator== (const node& other) const
{
return sa==other.sa && sb==other.sb && sc==other.sc;
}
};
struct SplayNode
{
SplayNode *ch[2], *p;
node n, o;
int k;
void init(long long k, node o)
{
ch[0]=ch[1]=p=nullptr;
this->k=k;
this->n=this->o=o;
}
} pool[2000000];
int npool;
void maintain(SplayNode *n)
{
n->n=n->o;
for(int i=0; i<2; i++) if(n->ch[i])
{
n->ch[i]->p=n;
n->n+=n->ch[i]->n;
}
}
int child(SplayNode *n)
{
if(n->p)
{
if(n->p->ch[0]==n)
return 0;
if(n->p->ch[1]==n)
return 1;
}
return -1;
}
void rotate_up(SplayNode *n)
{
SplayNode *p=n->p;
int d=child(n);
int pd=child(p);
assert(d!=-1);
p->ch[d]=n->ch[d^1];
n->ch[d^1]=p;
n->p=p->p;
maintain(p);
maintain(n);
if(pd!=-1)
{
n->p->ch[pd]=n;
maintain(n->p);
}
}
void splay(SplayNode *n)
{
while(child(n)!=-1)
{
if(child(n->p)==-1)
rotate_up(n);
else
{
if(child(n)!=child(n->p))
rotate_up(n), rotate_up(n);
else
rotate_up(n->p), rotate_up(n);
}
}
}
void insert(SplayNode *n, SplayNode *t)
{
if(t->k<n->k)
{
if(!n->ch[0])
n->ch[0]=t;
else
insert(n->ch[0], t);
}
else
{
if(!n->ch[1])
n->ch[1]=t;
else
insert(n->ch[1], t);
}
maintain(n);
}
SplayNode *lastTouch;
node ask(SplayNode *n, int k)
{
if(!n)
return node();
lastTouch=n;
if(k<n->k)
return ask(n->ch[0], k);
node ret=n->o;
if(n->ch[0])
ret+=n->ch[0]->n;
ret+=ask(n->ch[1], k);
return ret;
}
int N, M, K;
pair<int, int> A[100000];
int X[200000];
int L[100000];
int R[100000];
int fsize[200001];
int ok;
vector<long long> dp[351];
SplayNode* bit[200001];
struct dac
{
int l, r, optL, optR;
tuple<int, int, int, int> mt() const
{
return make_tuple(l, r, optL, optR);
}
};
struct query
{
int m, x, y, i, xc, yc;
bool operator< (const query& other) const
{
return m<other.m;
}
} B[100000];
const int MAGIC=1500;
long long val[200000];
long long val2[200000];
vector<node> blt[200001];
void add_point(int x, int y, node n)
{
x=M-1-x;
for(int i=x+1; i<=M; i+=i&-i)
{
if(ok && fsize[i]>=MAGIC)
{
for(int j=y+1; j<=M; j+=j&-j)
blt[i][j]+=n;
continue;
}
if(!ok)
fsize[i]++;
SplayNode *t=&pool[npool++];
if(npool==2000000)
npool=0;
t->init(y+1, n);
if(bit[i])
{
insert(bit[i], t);
splay(t);
}
bit[i]=t;
}
}
void era_point(int x, int y)
{
x=M-1-x;
for(int i=x+1; i<=M; i+=i&-i)
{
if(ok && fsize[i]>=MAGIC)
{
for(int j=y+1; j<=M; j+=j&-j)
blt[i][j]=node();
continue;
}
}
}
node ask_point(int x, int y)
{
x=M-1-x;
node n;
for(int i=x+1; i>0; i-=i&-i)
{
if(ok && fsize[i]>=MAGIC)
{
for(int j=y+1; j>0; j-=j&-j)
n+=blt[i][j];
continue;
}
if(bit[i])
{
n+=ask(bit[i], y+1);
bit[i]=lastTouch;
splay(bit[i]);
}
}
return n;
}
void solve(int i, int l, int r, int optL, int optR)
{
if(l>r)
return;
vector<dac> q, nq;
q.push_back((dac){l, r, optL, optR});
while(!q.empty())
{
for(int j=1; j<=M; j++)
{
bit[j]=nullptr;
if(ok && fsize[j]>=MAGIC)
{
if((int)blt[j].size()!=M+1)
blt[j].resize(M+1);
fill(blt[j].begin(), blt[j].end(), node());
}
}
vector<query> queries;
int nqueries=0;
for(auto& it: q)
{
tie(l, r, optL, optR)=it.mt();
int j=(l+r)/2;
dp[i][j]=0x3f3f3f3f3f3f3f3fLL;
for(int k=min(optR, j-1); k>=optL; k--)
{
val[nqueries]=dp[i-1][k];
queries.push_back((query){X[k]+X[j], X[k], X[j], nqueries++, k, j});
}
}
sort(queries.begin(), queries.end());
int l=0;
for(int k=0; k<(int)queries.size(); k++)
{
for(; l<N && B[l].m<queries[k].m; l++)
add_point(B[l].xc, B[l].yc, (node){B[l].m, B[l].y, 1});
node n=ask_point(queries[k].xc, queries[k].yc);
val[queries[k].i]+=n.sa;
val2[queries[k].i]=n.sc;
}
for(; l<N; l++)
add_point(B[l].xc, B[l].yc, (node){B[l].m, B[l].y, 1});
for(int k=0; k<(int)queries.size(); k++)
{
node n=ask_point(queries[k].xc, queries[k].yc);
val[queries[k].i]-=n.sb;
val[queries[k].i]-=1LL*n.sc*queries[k].x;
val[queries[k].i]+=queries[k].m*(n.sc-val2[queries[k].i]);
}
//for(l=0; l<N; l++)
//era_point(B[l].xc, B[l].yc);
nqueries=0;
for(auto& it: q)
{
tie(l, r, optL, optR)=it.mt();
int j=(l+r)/2;
dp[i][j]=0x3f3f3f3f3f3f3f3fLL;
int opt=0;
for(int k=min(optR, j-1); k>=optL; k--)
{
if(val[nqueries]<dp[i][j])
{
opt=k;
dp[i][j]=val[nqueries];
}
nqueries++;
}
if(l<=j-1)
nq.push_back((dac){l, j-1, optL, opt});
if(j+1<=r)
nq.push_back((dac){j+1, r, opt, optR});
}
q.swap(nq);
nq.clear();
ok=1;
}
}
int main()
{
scanf("%d%d", &N, &K);
//K = 3;
//N = 100000 / K;
long long ans=0;
for(int i=0; i<N; i++)
{
//A[i].first=rand()*10000+rand();
//A[i].second=rand()*10000+rand();
scanf("%d%d", &A[i].first, &A[i].second);
if(A[i].first>A[i].second)
swap(A[i].first, A[i].second);
ans+=A[i].second-A[i].first;
}
sort(A, A+N, [](const pair<int, int>& a, const pair<int, int>& b) {
if(a.second!=b.second)
return a.second<b.second;
return a.first<b.first;
});
for(int i=0; i<N; i++)
{
tie(L[i], R[i])=A[i];
X[i*2]=L[i];
X[i*2+1]=R[i];
}
sort(X, X+2*N);
M=unique(X, X+2*N)-X;
for(int i=0; i<N; i++)
{
int xc=lower_bound(X, X+M, L[i])-X;
int yc=lower_bound(X, X+M, R[i])-X;
B[i]=(query){L[i]+R[i], L[i], R[i], i, xc, yc};
}
sort(B, B+N);
for(int i=1; i<=K; i++)
dp[i].resize(M);
long long SR=0, NR=0;
for(int i=0, j=0; i<M; i++)
{
for(; j<N && R[j]<X[i]; j++)
SR+=R[j], NR++;
dp[1][i]=NR*X[i]-SR;
}
int flag=0;
if(K==3 && M>=59000)
{
time_t tt=-clock();
for(int i=2; i<=K-1; i++)
solve(i, i-1, M-1, i-2, M-1);
tt+=clock();
if(tt>=CLOCKS_PER_SEC)
{
solve(3, 3*M/4, M-1, 2, M/2+50);
flag=1;
}
else
solve(3, 2, M-1, 1, M-1);
}
else
{
for(int i=2; i<=K; i++)
solve(i, i-1, M-1, i-2, M-1);
}
sort(L, L+N, greater<int>());
long long SL=0, NL=0;
long long ans2=0x3f3f3f3f3f3f3f3fLL;
if(flag)
{
for(int i=M-1, j=0; i>=3*M/4; i--)
{
for(; j<N && L[j]>X[i]; j++)
SL+=L[j], NL++;
ans2=min(ans2, dp[K][i]+SL-NL*X[i]);
}
}
else
{
for(int i=M-1, j=0; i>=K-1; i--)
{
for(; j<N && L[j]>X[i]; j++)
SL+=L[j], NL++;
ans2=min(ans2, dp[K][i]+SL-NL*X[i]);
}
}
cout << ans + ans2 * 2 << endl;
return 0;
}
In Java :
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static HD[] hdds;
static Point[] points;
static int n, k;
static long[][] f;
static long[] g;
static long totalLength;
static SegmentTree stHD;
static PersistentSegmentTree pst;
static Vertex[] rootsPST;
static boolean dist;
static long[] prefR;
static long[] prefL;
static Calc calc;
static class HD {
int left, right, length;
Point pL, pR;
long mid;
int index;
public HD(int left, int right) {
boolean b = left > right;
this.left = b ? right : left;
this.right = b ? left : right;
mid = (left + right);
length = (this.right - this.left);
}
@Override
public String toString() {
return left + " " + right + " " + mid;
}
}
static class Point {
HD hd;
int point;
int sortIndex;
public Point(HD hd, boolean isLeft) {
this.hd = hd;
point = isLeft ? hd.left : hd.right;
}
@Override
public String toString() {
return hd.left + " " + hd.right + " " + point;
}
}
static interface Calc {
public long getW(int start, int end);
}
static class Pair {
int nL, nR;
long sumL, sumR;
public Pair(int nR, int nL, long sumR, long sumL) {
this.nR = nR;
this.nL = nL;
this.sumR = sumR;
this.sumL = sumL;
}
}
static class Node {
int[] valueSLe;
int[] valueSRi;
long[] sumParR;
long[] sumParL;
int size;
int nL, nR;
public Node() {
}
}
static class SegmentTree {
Node[] t;
SegmentTree(int n) {
t = new Node[4 * n];
for (int i = 0; i < 4 * n; i++) {
t[i] = new Node();
}
}
void build(HD[] a, int v, int tl, int tr) {
if (tl == tr) {
t[v].valueSLe = new int[1];
t[v].valueSRi = new int[1];
t[v].valueSRi[0] = a[tl + 1].pR.point;
t[v].valueSLe[0] = a[tl + 1].pL.point;
t[v].size = 1;
t[v].sumParL = new long[1];
t[v].sumParL[0] = a[tl + 1].left;
t[v].sumParR = new long[1];
t[v].sumParR[0] = a[tl + 1].right;
} else {
int tm = (tl + tr) / 2;
build(a, v * 2, tl, tm);
build(a, v * 2 + 1, tm + 1, tr);
t[v].size = t[v * 2].size + t[v * 2 + 1].size;
merge(v);
}
}
private void merge(int v) {
t[v].valueSLe = new int[t[v].size];
t[v].valueSRi = new int[t[v].size];
t[v].sumParL = new long[t[v].size];
t[v].sumParR = new long[t[v].size];
mergeAInt(t[v].valueSLe, t[2 * v].valueSLe, t[2 * v + 1].valueSLe);
mergeAInt(t[v].valueSRi, t[2 * v].valueSRi, t[2 * v + 1].valueSRi);
updateCS(t[v]);
}
private void updateCS(Node node) {
long[] sumParLu = new long[node.size];
long[] sumParRu = new long[node.size];
int[] valueL = node.valueSLe;
int[] valueR = node.valueSRi;
sumParLu[0] = valueL[0];
sumParRu[0] = valueR[0];
for (int i = 1; i < node.size; i++) {
sumParLu[i] = sumParLu[i - 1] + valueL[i];
sumParRu[i] = sumParRu[i - 1] + valueR[i];
}
node.sumParL = sumParLu;
node.sumParR = sumParRu;
}
static long[] ZERO = new long[] { 0, 0, 0, 0 };
void query(int v, int tl, int tr, int l, int r, int p, long[] fResults) {
if (l > r || tr < l || tl > r) {
return;
}
if (l == tl && tr == r) {
Node node = t[v];
int size = node.size;
long[] sPL = node.sumParL;
int limU = upperBound(node.valueSRi, p);
int limL = lowerBound(node.valueSLe, p);
int nR = limU == -1 ? 0 : limU + 1;
long sumR = limU == -1 ? 0 : node.sumParR[limU];
int nL = limL == size ? 0 : size - limL;
long sumL = limL == size ? 0 : sPL[size - 1] - (limL == 0 ? 0 : sPL[limL - 1]);
fResults[0] += nR;
fResults[1] += nL;
fResults[2] += sumR;
fResults[3] += sumL;
return;
}
int tm = (tl + tr) / 2;
query(v * 2, tl, tm, l, Math.min(r, tm), p, fResults);
query(v * 2 + 1, tm + 1, tr, Math.max(l, tm + 1), r, p, fResults);
}
}
static class Vertex {
Vertex l, r;
int count;
Vertex(int val) {
count = val;
}
Vertex(Vertex l, Vertex r) {
this.l = l;
this.r = r;
if (l != null)
count += l.count;
if (r != null)
count += r.count;
}
};
static class PersistentSegmentTree {
Vertex build(int tl, int tr) {
if (tl == tr) {
return new Vertex(0);
}
int tm = (tl + tr) / 2;
return new Vertex(build(tl, tm), build(tm + 1, tr));
}
Vertex update(Vertex v, int tl, int tr, int pos) {
if (tl == tr) {
return new Vertex(1);
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
return new Vertex(update(v.l, tl, tm, pos), v.r);
} else {
return new Vertex(v.l, update(v.r, tm + 1, tr, pos));
}
}
int query(Vertex v1, Vertex v2, int b, int e, int x) {
if (b == e) {
return b;
}
int oo = v1.l.count - v2.l.count;
int mid = (b + e) / 2;
if (oo >= x) {
return query(v1.l, v2.l, b, mid, x);
} else {
return query(v1.r, v2.r, mid + 1, e, x - oo);
}
}
}
static void mergeAInt(int[] values, int[] values1, int[] values2) {
int n1 = values1.length;
int n2 = values2.length;
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
int p1 = values1[i];
int p2 = values2[j];
if (p1 <= p2) {
i++;
values[k++] = p1;
} else {
j++;
values[k++] = p2;
}
}
while (i < n1) {
values[k++] = values1[i++];
}
while (j < n2) {
values[k++] = values2[j++];
}
}
static private int upperBound(int[] arr, int endV) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (arr[mid] <= endV) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
static private int lowerBound(int[] arr, int startV) {
int left = 0;
int al = arr.length;
int right = al - 1;
while (left <= right) {
int mid = (right + left) / 2;
if (arr[mid] >= startV) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
private static void initW() {
f = new long[k + 1][n + 1];
g = new long[n + 2];
Arrays.sort(hdds, 1, n + 1, new Comparator<HD>() {
@Override
public int compare(HD o1, HD o2) {
long d = o1.mid - o2.mid;
if (d != 0) {
return d < 0 ? -1 : 1;
} else {
return o1.left - o2.left;
}
}
});
SASD sd = new SASD();
dist = true;
for (int j = 1; j <= n; j++) {
sd.add(hdds[j]);
f[1][j] = sd.ans;
if (j < n && hdds[j].right > hdds[j + 1].left) {
dist = false;
}
}
if (!dist) {
calc = new Calc() {
@Override
public long getW(int start, int end) {
return getW1(start, end);
}
};
Point[] pointsToSort = new Point[2 * n];
for (int j = 1; j <= n; j++) {
HD hd = hdds[j];
hd.index = j;
Point p = new Point(hd, true);
hd.pL = p;
pointsToSort[2 * j - 2] = p;
p = new Point(hd, false);
hd.pR = p;
pointsToSort[2 * j - 1] = p;
}
Arrays.sort(pointsToSort, 0, 2 * n, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
long d = o1.point - o2.point;
if (d != 0) {
return d < 0 ? -1 : 1;
} else {
return o1.hd.index - o2.hd.index;
}
}
});
points = new Point[2 * n];
for (int j = 0; j < 2*n; j++) {
Point p = pointsToSort[j];
p.sortIndex = j;
points[j] = p;
}
stHD = new SegmentTree(n);
stHD.build(hdds, 1, 0, n - 1);
rootsPST = new Vertex[n+1];
pst = new PersistentSegmentTree();
rootsPST[0] = pst.build(0, 2*n-1);
for (int j = 1; j <= n; j++) {
Vertex root = pst.update(rootsPST[j-1], 0, 2*n-1, hdds[j].pL.sortIndex);
rootsPST[j] = pst.update(root, 0, 2*n-1, hdds[j].pR.sortIndex);
}
} else {
calc = new Calc() {
@Override
public long getW(int start, int end) {
return getW2(start, end);
}
};
prefL = new long[n + 1];
prefR = new long[n + 1];
for (int j = 1; j <= n; j++) {
prefR[j] = prefR[j - 1] + hdds[j].right;
prefL[j] = prefL[j - 1] + hdds[j].left;
}
}
}
static Map<Integer, Long>[] memo;
private static long getW1(int jStart, int jEnd) {
Long ans = memo[jEnd].get(jStart);
if (ans != null) {
return ans;
}
int mid = pst.query(rootsPST[jEnd], rootsPST[jStart-1], 0, 2 * n - 1, jEnd-jStart+1);
int p = points[mid].point;
long[] pair = new long[4];
stHD.query(1, 0, n - 1, jStart - 1, jEnd - 1, p, pair);
ans = p * pair[0] - pair[2] + pair[3] - p * pair[1];
memo[jEnd].put(jStart, ans);
return ans;
}
private static long getW2(int jStart, int jEnd) {
int mid = (jStart + jEnd) / 2;
long p = hdds[mid].right;
long ans = p * (mid - jStart + 1) - (prefR[mid] - prefR[jStart - 1]) + (prefL[jEnd] - prefL[mid])
- p * (jEnd - mid);
return ans;
}
static int INF = 2000000000;
static class SASD {
int mid1 = -INF;
int mid2 = INF;
long ans;
private PriorityQueue<Integer> r = new PriorityQueue<Integer>();
void add(HD hd) {
int nLow = hd.left;
int nHigh = hd.right;
if (nLow >= mid2) {
ans += (nLow - mid2);
r.remove();
r.add(nLow);
r.add(nHigh);
mid1 = mid2;
mid2 = r.peek();
} else if (nLow < mid1) {
r.add(nHigh);
} else {
r.add(nHigh);
mid1 = nLow;
if (mid2 == INF) {
mid2 = nHigh;
}
if (nHigh <= mid2) {
mid2 = nHigh;
}
}
}
}
static class SADS {
int mid1 = -INF;
int mid2 = INF;
long ans;
private PriorityQueue<Integer> l = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
void add(HD hd) {
int nLow = hd.left;
int nHigh = hd.right;
if (nHigh <= mid1) {
ans += (mid1 - nHigh);
l.remove();
l.add(nLow);
l.add(nHigh);
mid2 = mid1;
mid1 = l.peek();
} else if (nHigh > mid2) {
l.add(nLow);
if (nLow >= mid2) {
ans += (nHigh - mid2);
}
} else {
l.add(nLow);
mid2 = nHigh;
if (mid1 == -INF) {
mid1 = nLow;
}
if (nLow >= mid1) {
mid1 = nLow;
}
}
}
}
//static int c = 0;
//static long time = 0;
static long hardDrive() {
if (k == n) {
return totalLength;
}
initW();
if (f[1][n] == 0) {
return totalLength;
}
int STEEP = 10;
SADS ds = new SADS();
long ans = f[1][n];
int minG = 1;
for (int s = n; s >= 1; s--) {
ds.add(hdds[s]);
g[s] = ds.ans;
long pAns = f[1][s - 1] + ds.ans;
if (pAns < ans) {
ans = pAns;
minG = s;
}
}
f[2][n] = ans;
if (k == 2) {
return 2 * ans + totalLength;
}
long fRMIN = 0;
int[] minAJ = new int[n + 1];
Arrays.fill(minAJ, 1);
for (int i = 2; i < k; i++) {
if (i == k - 1) {
ans = f[i - 1][n];
int lower = minG;
int higher = n;
if (higher > lower + STEEP) {
Pair p = search(calc, i, n, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + g[s];
if (pAns < ans) {
ans = pAns;
minG = s;
}
}
f[i][n] = ans;
fRMIN = ans;
int minG2 = n;
minG = minG > 1 ? minG - 1 : 1;
int fSteep = 100;
for (int j = minG; j <= minG2; j++) {
ans = f[i - 1][j];
lower = 1;
higher = j;
if (higher > lower + STEEP) {
Pair p = search(calc, i, j, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
if (f[i - 1][lower - 1] != f[i - 1][higher - 1]) {
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + calc.getW(s, j);
if (pAns < ans) {
ans = pAns;
}
}
} else {
ans = f[i - 1][higher - 1] + calc.getW(higher, j);
}
f[i][j] = ans;
long pFA = ans + g[j + 1];
if (pFA < fRMIN) {
fRMIN = pFA;
}
if (ans >= fRMIN) {
break;
}
if (j + fSteep <= minG2 && ans + g[j + fSteep] >= fRMIN) {
j = j + fSteep;
}
while (j < minG2 && g[j+1] == g[j+2]) {
j++;
}
}
} else {
for (int j = i + 1; j < n; j++) {
ans = f[i - 1][j];
int nMin = minAJ[j];
int lower = nMin;
int higher = j;
if (higher > lower + STEEP) {
Pair p = search(calc, i, j, lower, higher, STEEP);
ans = p.sumR;
lower = p.nR;
higher = p.nL;
}
if (f[i - 1][lower - 1] != f[i - 1][higher - 1]) {
for (int s = lower; s <= higher; s++) {
long pAns = f[i - 1][s - 1] + calc.getW(s, j);
if (pAns < ans) {
ans = pAns;
nMin = s;
}
}
} else {
ans = f[i - 1][higher - 1] + calc.getW(higher, j);
}
f[i][j] = ans;
minAJ[j] = nMin;
}
}
}
return 2 * fRMIN + totalLength;
}
static Pair search(Calc calc, int i, int j, int lower, int higher, int steep) {
long ans = 0;
while (higher > lower + steep) {
int mid = (lower + higher) / 2;
int mid1 = (lower + mid) / 2;
mid1 = mid1 % 2 == 0 ? mid1 : mid1 + 1;
int mid2 = (higher + mid) / 2;
mid2 = mid2 % 2 == 0 ? mid2 : mid2 - 1;
long res1 = f[i - 1][mid1 - 1] + calc.getW(mid1, j);
long res2 = f[i - 1][mid2 - 1] + calc.getW(mid2, j);
if (res1 < res2) {
higher = mid2 - 1;
ans = res1;
} else if (res1 >= res2) {
lower = mid1 + 1;
ans = res2;
}
}
return new Pair(lower, higher, ans, 0);
}
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 2 * 4096 * 4096);
String[] nk = reader.readLine().trim().split(" ");
n = Integer.parseInt(nk[0]);
k = Integer.parseInt(nk[1]);
hdds = new HD[n + 1];
totalLength = 0;
for (int hddsRowItr = 1; hddsRowItr <= n; hddsRowItr++) {
String[] hddsRowItems = reader.readLine().trim().split(" ");
HD hd = new HD(Integer.parseInt(hddsRowItems[0]), Integer.parseInt(hddsRowItems[1]));
hdds[hddsRowItr] = hd;
totalLength += hd.length;
}
memo = new Map[n+1];
for (int j = 1; j <= n; j++) {
memo[j] = new HashMap<Integer, Long>();
}
dist = true;
long result = hardDrive();
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
reader.close();
}
}
View More Similar Problems
Castle on the Grid
You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):
View Solution →Down to Zero II
You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.
View Solution →Truck Tour
Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr
View Solution →Queries with Fixed Length
Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon
View Solution →QHEAP1
This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element
View Solution →Jesse and Cookies
Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t
View Solution →