結果

問題 No.705 ゴミ拾い Hard
ユーザー 夕叢霧香(ゆうむらきりか)
提出日時 2018-05-18 00:37:42
言語 Java
(openjdk 23)
結果
AC  
実行時間 703 ms / 1,500 ms
コード長 4,486 bytes
コンパイル時間 2,572 ms
コンパイル使用メモリ 78,612 KB
実行使用メモリ 75,784 KB
最終ジャッジ日時 2024-06-28 13:38:39
合計ジャッジ時間 18,358 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.*;
import java.util.*;
class Main {
static long cube(long x){return x*x*x;}
Main(){}
long[] solveNaive(long[]a,long[]x,long[]y){
int n=a.length;
long[]dp=new long[n+1];
Arrays.fill(dp,Long.MAX_VALUE);
dp[0]=0;
for(int i=0;i<n;++i){
for(int j=0;j<=i;++j){
dp[i+1]=Math.min(dp[i+1],
dp[j]+cube(Math.abs(a[i]-x[j]))+cube(y[j]));
}
}
return dp;
}
/*
* i < j
*/
int calculateReversePoint(long[]a,long[]x,long[]y,int i,int j,long[]dp){
int n=a.length;
int pass=n,fail=j-1;
while(pass-fail>1){
int middle=(pass+fail)/2;
long value1=dp[i]+cube(Math.abs(a[middle]-x[i]))+cube(y[i]);
long value2=dp[j]+cube(Math.abs(a[middle]-x[j]))+cube(y[j]);
if(value1>=value2)pass=middle;
else fail=middle;
}
return pass;
}
long[] solveMongeDP(long[]a,long[]x,long[]y){
int n=a.length;
long[]dp=new long[n+1];
Arrays.fill(dp,Long.MAX_VALUE);
dp[0]=0;
int[]deq=new int[n+1];
int[]rev=new int[n+1];
int s=0,t=0;
for(int i=0;i<n;++i){
if(false){
System.err.println("deq:");
for(int j=s;j<t;++j){
System.err.print("("+deq[j]+","+rev[j]+") ");
}
System.err.println();
}
int pre=i;
long value=dp[pre]+cube(Math.abs(a[i]-x[pre]))+cube(y[pre]);
//System.err.println("C("+pre+","+(i+1)+")="+value);
// TODO imperfect
while(s<t){
int oldPre=deq[t-1];
int revPoint=calculateReversePoint(a,x,y,oldPre,i,dp);
long oldValue=dp[oldPre]+cube(Math.abs(a[i]-x[oldPre]))
+cube(y[oldPre]);
//System.err.println("C("+oldPre+","+(i+1)+")="+oldValue);
if(revPoint<=i)t--;
else if(t>=s+2&&rev[t-2]>=revPoint)t--;
else{
rev[t-1]=revPoint;
break;
}
}
while(s<t){
if(rev[s]<=i)s++;
else break;
}
deq[t]=i;
t++;
pre=deq[s];
value=dp[pre]+cube(Math.abs(a[i]-x[pre]))+cube(y[pre]);
dp[i+1]=value;
}
return dp;
}
public static void main(String[] args) {
MyScanner sc = new MyScanner();
out = new PrintWriter(new BufferedOutputStream(System.out));
int n=sc.nextInt();
long[]a=sc.nextLongArray(n);
long[]x=sc.nextLongArray(n);
long[]y=sc.nextLongArray(n);
Main solver=new Main();
//long[]dp=solver.solveNaive(a,x,y);
long[]dpMonge=solver.solveMongeDP(a,x,y);
//System.err.println(Arrays.toString(dp));
//System.err.println(Arrays.toString(dpMonge));
out.println(dpMonge[n]);
out.close();
}
// http://codeforces.com/blog/entry/7018
//-----------PrintWriter for faster output---------------------------------
public static PrintWriter out;
//-----------MyScanner class for faster input----------
public static class MyScanner {
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
long[] nextLongArray(int n){
long[]r=new long[n];
for(int i=0;i<n;++i)r[i]=nextLong();
return r;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0