Maybe it's the limitation of the programming language?
Difference between en1 and en2, changed 24 character(s)
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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English YocyCraft 2023-01-11 19:57:37 4 Tiny change: 'problem:1775F] in whic' -> 'problem:1768F] in whic'
en3 English YocyCraft 2023-01-11 19:56:51 1 Tiny change: '88424856] (483ms) wh' -> '88424856] _(483ms) wh'
en2 English YocyCraft 2023-01-11 19:54:59 24 Tiny change: '.util.*;\nimport java.io.*;\npublic c' -> '.util.*;\n\nimport java.io.*;\n\npublic c'
en1 English YocyCraft 2023-01-11 19:52:25 2842 Initial revision (published)