java-competitive/archive/2017.04/2017.04.30 - unsorted/TaskB.java

package chelper;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import io.InputReader;
import io.OutputWriter;
import misc.GCJSolution;


public class TaskB extends GCJSolution {

  public void solve(int testNumber, InputReader in, OutputWriter out) {
    wrapSolve(testNumber, in, out);
  }

  class Interval implements Comparable<Interval> {
    int start;
    int end;
    int kind;
    int len;

    public Interval(int start, int end, int kind) {
      this.start = start;
      this.end = end;
      this.kind = kind;
      len = end - start;
    }

    @Override
    public int compareTo(Interval o) {
      return Integer.compare(start, o.start);
    }

    @Override
    public String toString() {
      return "Interval{" +
          "start=" + start +
          ", end=" + end +
          ", kind=" + kind +
          ", len=" + len +
          '}';
    }
  }

  int BIG = 1000000;

  int[] makeDp() {
    int[] dp = new int[721];
    Arrays.fill(dp, BIG);
    return dp;
  }

  @Override
  public void solve(int testNumber) {
    System.out.println("Test " + testNumber);
    System.out.flush();

    List<Interval> intervals = new ArrayList<>();

    int a1 = in.nextInt();
    int a2 = in.nextInt();

    for (int i = 0; i < a1; i++) {
      intervals.add(new Interval(in.nextInt(), in.nextInt(), 0));
    }
    for (int i = 0; i < a2; i++) {
      intervals.add(new Interval(in.nextInt(), in.nextInt(), 1));
    }

    int[] dp = makeDp();
    int[] newDp;

    dp[0] = 0;

    Collections.sort(intervals);

    intervals.add(new Interval(intervals.get(0).start + 1440, intervals.get(0).end + 1440, intervals.get(0).kind));

    int totalTaken = 0;

    for (int intervalI = 0; intervalI < intervals.size() - 1; intervalI++) {
      Interval x = intervals.get(intervalI);
      int k = x.kind;

      {
        newDp = makeDp();
        for (int aTaken = 0; aTaken <= 720; aTaken++) {
          int bTaken = totalTaken - aTaken;

          if (bTaken < 0 || dp[aTaken] == BIG) {
            continue;
          }

          int aTaken2 = aTaken + (k == 0 ? x.len : 0);
          int bTaken2 = bTaken + (k == 1 ? x.len : 0);

          if (aTaken2 > 720 || bTaken2 > 720) {
            continue;
          }

          newDp[aTaken2] = dp[aTaken];
        }
        totalTaken += x.len;
        dp = newDp;
      }

      Interval next = intervals.get(intervalI + 1);
      int k2 = next.kind;
      int dist = next.start - x.end;

      {
        newDp = makeDp();
        for (int aTaken = 0; aTaken <= 720; aTaken++) {
          int bTaken = totalTaken - aTaken;
          if (bTaken < 0 || dp[aTaken] == BIG) {
            continue;
          }

          for (int aAdd = 0; aAdd <= dist; aAdd++) {
            int bAdd = dist - aAdd;

            int penalty = 0;

            if (k != k2) {
              penalty = 1;
            } else {
              if (k == 0 && bAdd > 0) {
                penalty = 2;
              }
              if (k == 1 && aAdd > 0) {
                penalty = 2;
              }
            }

            int aTaken2 = aTaken + aAdd;
            int bTaken2 = bTaken + bAdd;

            if (aTaken2 > 720 || bTaken2 > 720) {
              continue;
            }

            newDp[aTaken2] = Math.min(newDp[aTaken2], dp[aTaken] + penalty);
          }
        }
        totalTaken += dist;
        dp = newDp;
      }
    }

    int ans = BIG;
    for (int i = 0; i <= 720; i++) {
      ans = Math.min(ans, dp[i]);
    }
    out.println(ans);
  }
}