By skurada, history, 6 weeks ago,

Hello, I am trying to complete the CSES DP Problem Set and am working on the last problem Projects. I am working in JAVA, and my solution is TLE-ing out on the larger cases. I am not sure how to optimize my code, I believe it should run in O(n log n). Could someone please help me get my code working in time?

import java.util.*;
import java.io.*;

public class Projects {

public StringTokenizer tokenizer;

tokenizer = null;
}

public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
} catch (IOException e) {
throw new RuntimeException(e);
}
}
}

public int nextInt() {
return Integer.parseInt(next());
}

public float nextFloat() {
return Float.parseFloat(next());
}

public double nextDouble() {
return Float.parseFloat(next());
}

public long nextLong() {
return Long.parseLong(next());
}
}

static class CPMath {
static int add(int a, int b) {
a += b;

if (a >= mod) a -= mod;

return a;
}

static int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}

static int multiply(int a, long b) {
b = a * b;
return (int) (b % mod);
}

static int divide(int a, int b) {
return multiply(a, inverse(b));
}

static int inverse(int a) {
return power(a, mod - 2);
}

static int power(int a, int b) {
int r = 1;

while (b > 0) {
if (b % 2 == 1) {
r = multiply(r, a);
}

a = multiply(a, a);
b /= 2;
}

return r;
}
}

static PrintWriter pw;

static int mod = (int) (1e9 + 7);

static ArrayList<Pair>[] arrayLists;

public static void main(String[] args) throws Exception {
pw = new PrintWriter(System.out);

int n = sc.nextInt();

HashSet<Integer> hashSet = new HashSet<>();
ArrayList<Integer> points = new ArrayList<>();

Pair[] pairs = new Pair[n];

for (int i = 0; i < n; i++) {
int start = sc.nextInt();
int end = sc.nextInt() + 1;
long value = sc.nextLong();

Pair p = new Pair(start, value, end);
pairs[i] = p;

if (!hashSet.contains(start)) {
}
if (!hashSet.contains(end)) {
}
}

assert points.size() != hashSet.size();
assert points.size() < 2e5 + 5;

Collections.sort(points);

arrayLists = new ArrayList[points.size()];

for (int i = 0; i < points.size(); i++) {
arrayLists[i] = new ArrayList<>();
}

for (int i = 0; i < pairs.length; i++) {
Pair p = pairs[i];

int sI = Collections.binarySearch(points, p.start);
int sE = Collections.binarySearch(points, p.end);

p.start = sI;
p.end = sE;

}

long[] dp = new long[points.size()];

for (int i = 0; i < points.size(); i++) {
if (i != 0) dp[i] = dp[i - 1];

for (Pair p: arrayLists[i]) {
dp[i] = Math.max(dp[i], dp[p.start] + p.value);
}
}

pw.println(dp[points.size() - 1]);
pw.close();
}

static class Pair {
int start, end;
long value;

Pair(int start, long value, int end) {
this.start = start;
this.value = value;
this.end = end;
}
}
}


• -1

 » 6 weeks ago, # |   0 for (int i = 0; i < points.size(); i++) { if (i != 0) dp[i] = dp[i - 1]; for (Pair p: arrayLists[i]) { dp[i] = Math.max(dp[i], dp[p.start] + p.value); } } what is the complexity of the above code? Also, you should point to the problem link.