Submission #1022612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022612		idante	Art Exhibition (JOI18_art)	Java	100 / 100	949 ms	109128 KiB

art

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

public class art {

  public static void main(String[] args) throws IOException {
    BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

    long n = Long.parseLong(r.readLine());
    List<Artwork> a = new ArrayList<>();
    for (long i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(r.readLine());

      long x = Long.parseLong(st.nextToken());
      long y = Long.parseLong(st.nextToken());
      a.add(new Artwork(x, y));
    }

    // sort based off of size of the artworks
    a.sort(Comparator.comparingLong(artwork -> artwork.size));

    // prefix sum list
    List<Long> p = new ArrayList<>(Collections.nCopies((int) n, 0L));

    p.set(0, a.get(0).value);
    for (int i = 1; i < n; i++) {
      // update the prefix sum
      p.set(i, p.get(i - 1) + a.get(i).value);
    }

    long cur;
    long res = 0;

    // holds differences between prefix sums
    TreeSet<Long> m = new TreeSet<>();
    for (int i = (int) n - 1; i >= 0; i--) {
      // sum of all up to i - current size
      // i is the largest (A.max)
      m.add(p.get(i) - a.get(i).size);

      // get the maximum difference so far
      cur = m.last() - (i > 0 ? p.get(i - 1) : 0);

      // finish the expression
      cur += a.get(i).size;

      // are we larger?
      res = Math.max(res, cur);
    }
    System.out.println(res);
  }

  static class Artwork {

    long size, value;

    Artwork(long size, long value) {
      this.size = size;
      this.value = value;
    }
  }
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50