| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 335776 | Agnimandur | Discharging (NOI20_discharging) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.util.*;
import java.io.*;
public class Discharging {
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int ni() throws IOException {
int ret = 0;
boolean flip = false;
byte c = read();
while (c < '0' || c > '9') {
if (c == '-') flip = true;
c = read();
}
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return flip ? -ret : ret;
}
public long nl() throws IOException {
long ret = 0;
boolean flip = false;
byte c = read();
while (c < '0' || c > '9') {
if (c == '-') flip = true;
c = read();
}
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return flip ? -ret : ret;
}
private void fillBuffer() throws IOException
{
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1) {
buffer[0] = -1;
}
}
private byte read() throws IOException
{
if (bufferPointer == bytesRead) {
fillBuffer();
}
return buffer[bufferPointer++];
}
}
public static void main(String[] args) throws IOException {
Reader sc = new Reader();
PrintStream out = new PrintStream(new BufferedOutputStream(System.out));
int N = sc.ni();
long[] nums = new long[N+1];
for (int i = 1; i <= N; i++) {
nums[i] = Math.max(nums[i-1],sc.nl());
}
//dp with convex hull trick
long[] dp = new long[N+1];
Hull cht = new Hull();
for (int i = 1; i <= N; i++) {
cht.add(new Line(nums[N-(i-1)],dp[i-1]));
dp[i] = cht.getMin(i);
}
out.print(dp[N]);
out.flush(); // remember to flush just once, at the very end of your program
}
//convex hull
static class Hull {
ArrayDeque<Line> ad;
public Hull() {
ad = new ArrayDeque<Line>();
}
public void add(Line l) {
if (ad.isEmpty() || l.m < ad.peekLast().m) {
while (ad.size() >= 2) {
Line l1 = ad.pollLast();
Line l2 = ad.peekLast();
if (good(l2,l1,l)) {
ad.addLast(l1);
break;
}
}
ad.addLast(l);
}
}
public boolean good(Line l1, Line l2, Line l3) {
double d12 = (l2.b-l1.b+0.0)/(l1.m-l2.m);
double d23 = (l3.b-l2.b+0.0)/(l2.m-l3.m);
if (Math.abs(d12-d23) < 1e-10) {
BigInteger b12 = (new BigInteger(Long.toString(l2.b-l1.b))).multiply(new BigInteger(Long.toString(l2.m-l3.m)));
BigInteger b23 = (new BigInteger(Long.toString(l3.b-l2.b))).multiply(new BigInteger(Long.toString(l1.m-l2.m)));
if (b12.compareTo(b23) < 0)
return true;
else
return false;
} else {
return (d12 < d23);
}
}
public long getMin(long x) {
while (ad.size() >= 2) {
Line f1 = ad.pollFirst();
Line f2 = ad.peekFirst();
if ((f2.b-f1.b) > x*(f1.m-f2.m)) {
ad.addFirst(f1);
break;
}
}
return ad.peekFirst().eval(x);
}
}
//line
static class Line {
long m;
long b;
public Line(long m, long b) {
this.m=m;
this.b=b;
}
public long eval(long x) {
return m*x+b;
}
}
}