@Darklordx/

TEMPLATE-41

Java

No description

fork
loading
Files
  • Main.java
Main.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//TEMPLATE
import java.util.*;
import java.math.*;
public class Main {
    static Scanner scan;
    public static void println(Object s){System.out.println(s);}
    public static void print(Object s){System.out.print(s);}
    public static int nextInt(){return scan.nextInt();}
    public static long nextLong(){return scan.nextLong();}
    
    public static int nextIntL(){int i = scan.nextInt(); scan.nextLine(); return i;}
    public static long nextLongL(){long i = scan.nextLong(); scan.nextLine(); return i;}

    public static String nextLine(){return scan.nextLine();}
    
    static void println(int arr[]){
        printArray(arr);
    }
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i]+" "); 
        System.out.println(); 
    }

    public static void main(String[] args) {scan = new Scanner(System.in);solution();}

    //Solution goes below:
    public static void solution(){
        int raw = nextInt();
        int[] b = new int[raw];
        int n = -1;
        for(int i = 0; i<raw; i++){
            b[i] = nextInt();
            n = Math.max(n, b[i]);
        }
        //println(b);
        long[] a = new long[n+5];
        //Doesn't have to be long, but later for compatibility.

        for(int i:b){
            a[i+2]+=i; //min b is one, so preserves a[0-2].
        }
        //println(a);
        long[] lookup = new long[n+5];
        //Final ans will be in a[n+3].
        //a[0], a[1], a[2] = 0.
        for(int i = 3 ; i<n+5;i++){
            //println(lookup);
            lookup[i] = a[i]+Math.max(lookup[i-2], lookup[i-3]);
        }
        //println(lookup);
        println(lookup[n+4]);
    }

}