Today when I upsolving [problem:1775F] in which the intended solution is pretty simple. But the time complexity is O(n^1.5) and n=4*10^5 the time limit is pretty strict. I implemented the intended solution in java for many times but I always got TLE. Then I copied the submission [submission:188424856] (483ms) which is simpler the the official solution, and implemented in java, and got AC for 3322ms (My submission:[submission:188904779]). It seems that sometimes you must to optimize the solution further than intended.↵
↵
Also the official judge runs java code much more slowly than on my computer. I tested for cases where a[i]=1+(i%mod), where mod was about sqrt(400000). The code ran for about 0.6s but for the similar cases of the official judge it ran for about 2.3s.↵
↵
<spoiler summary="The code for testing time cost on my computer">↵
~~~~~↵
↵
import java.util.*;↵
import java.io.*;↵
public class Problem1768F {↵
↵
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));↵
↵
public static void main(String[] args) throws Exception {↵
long start = System.nanoTime();↵
↵
int n =400000; //Integer.parseInt(br.readLine());↵
long[] a = new long[n];↵
long[] dp=new long[n];↵
int mod=640;// also tested for 1000 and 320↵
for (int i = 0; i < n; i++) {↵
//Simulate the test case: 1 2 3 4 5 ...↵
a[i] =(i%mod)+1; //readInt();↵
dp[i]=2L*n*n;↵
}↵
dp[0]=0;↵
for(int i=0;i<n;i++) {↵
int lb=(int)Math.max(0,i-n/a[i]);↵
for(int j=i-1;j>=lb;j--) {↵
dp[i]=Math.min(dp[i], dp[j]+a[i]*(i-j)*(i-j));↵
if(a[i]>=a[j]) break;↵
}↵
int ub=(int)Math.min(n-1, i+n/a[i]);↵
for(int j=i+1;j<=ub;j++) {↵
dp[j]=Math.min(dp[j], dp[i]+a[i]*(j-i)*(j-i));↵
if(a[i]>=a[j]) break;↵
}↵
}↵
StringBuilder sb = new StringBuilder();↵
for(int i=0;i<n;i++) sb.append(dp[i]).append(' ');↵
↵
long end = System.nanoTime();↵
↵
//Tested for dozens of times. Max time cost is 0.63s↵
System.out.println((end - start) / 1E9);↵
↵
//System.out.println(sb);↵
}↵
↵
public static int readInt() {↵
int input = 0;↵
int c;↵
int sign = 1;↵
try {↵
while ((c = br.read()) == '-') {↵
sign = -sign;↵
}↵
input *= 10;↵
input += (c - 48);↵
while ((c = br.read()) > 32) {↵
input *= 10;↵
input += (c - 48);↵
}↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return (sign == 1) ? input : -input;↵
}↵
↵
public static long readLong() {↵
long input = 0;↵
int c;↵
int sign = 1;↵
try {↵
while ((c = br.read()) == '-') {↵
sign = -sign;↵
}↵
input *= 10;↵
input += (c - 48);↵
while ((c = br.read()) > 32) {↵
input *= 10;↵
input += (c - 48);↵
}↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return (sign == 1) ? input : -input;↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
↵
Also the official judge runs java code much more slowly than on my computer. I tested for cases where a[i]=1+(i%mod), where mod was about sqrt(400000). The code ran for about 0.6s but for the similar cases of the official judge it ran for about 2.3s.↵
↵
<spoiler summary="The code for testing time cost on my computer">↵
~~~~~↵
↵
import java.util.*;↵
import java.io.*;↵
public class Problem1768F {↵
↵
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));↵
↵
public static void main(String[] args) throws Exception {↵
long start = System.nanoTime();↵
↵
int n =400000; //Integer.parseInt(br.readLine());↵
long[] a = new long[n];↵
long[] dp=new long[n];↵
int mod=640;// also tested for 1000 and 320↵
for (int i = 0; i < n; i++) {↵
//Simulate the test case: 1 2 3 4 5 ...↵
a[i] =(i%mod)+1; //readInt();↵
dp[i]=2L*n*n;↵
}↵
dp[0]=0;↵
for(int i=0;i<n;i++) {↵
int lb=(int)Math.max(0,i-n/a[i]);↵
for(int j=i-1;j>=lb;j--) {↵
dp[i]=Math.min(dp[i], dp[j]+a[i]*(i-j)*(i-j));↵
if(a[i]>=a[j]) break;↵
}↵
int ub=(int)Math.min(n-1, i+n/a[i]);↵
for(int j=i+1;j<=ub;j++) {↵
dp[j]=Math.min(dp[j], dp[i]+a[i]*(j-i)*(j-i));↵
if(a[i]>=a[j]) break;↵
}↵
}↵
StringBuilder sb = new StringBuilder();↵
for(int i=0;i<n;i++) sb.append(dp[i]).append(' ');↵
↵
long end = System.nanoTime();↵
↵
//Tested for dozens of times. Max time cost is 0.63s↵
System.out.println((end - start) / 1E9);↵
↵
//System.out.println(sb);↵
}↵
↵
public static int readInt() {↵
int input = 0;↵
int c;↵
int sign = 1;↵
try {↵
while ((c = br.read()) == '-') {↵
sign = -sign;↵
}↵
input *= 10;↵
input += (c - 48);↵
while ((c = br.read()) > 32) {↵
input *= 10;↵
input += (c - 48);↵
}↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return (sign == 1) ? input : -input;↵
}↵
↵
public static long readLong() {↵
long input = 0;↵
int c;↵
int sign = 1;↵
try {↵
while ((c = br.read()) == '-') {↵
sign = -sign;↵
}↵
input *= 10;↵
input += (c - 48);↵
while ((c = br.read()) > 32) {↵
input *= 10;↵
input += (c - 48);↵
}↵
} catch (IOException e) {↵
e.printStackTrace();↵
}↵
return (sign == 1) ? input : -input;↵
}↵
}↵
↵
~~~~~↵
↵
</spoiler>↵
↵
