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;
}
}
Auto comment: topic has been updated by YocyCraft (previous revision, new revision, compare).
Once I've recieved a direct massage, which said like "Finally found a java coder with 2100+ rating, Thanks for existing because you're my inspiration". However sometimes I also need some inspiration... Especially when submitted intended solution and got TLE.
you mean you need a
second thread
to hold on to?What does "second thread" mean here?
He competes in Java only too:)
Some of the GMs/IGMs/LGMs primarily using Java/Kotlin are:
uwi
PavelKunyavskiy
Another User
Sumeet.Varma
Jeel_Vaishnav
Tlatoani
arvindf232
Petr was using Java for a very long time but apparently, he switched to C++ in 2019.
yeah, i remember there was bonus time for java to execute on some oj, but seems here is not.
I use kotlin but I believe Kotlin and Java are close enough for me to add something. I believe most of the difference could be explained by 32-bits vs 64-bits.
I am guessing that Kotlin 1.6 is 32 bits, and kotlin 1.7 (on CF) is 64 bits. All 64 bits operations (mostly modded multiplication) are ~2 times faster on Kotlin 1.7. Check 188108843. I have also observed the fact that Bitsets are twice as fast in kotlin1.7. Unfortunately, for most other operations 1.6 is faster by significant amount.
On the other hand, your local computer is almost certainly running 64 bits.
In contest, I got one penalty just by forgetting this and submitted with 1.6. See 188101349 vs 188101780. It fortunately did not cost me any ranks.
The existence of kotlin 1.7 had made so many TLE on modded problems no longer an issue.