package chelper; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; import io.InputReader; import io.OutputWriter; import misc.GCJSolution; import misc.SimpleSavingChelperSolution; public class TaskA extends GCJSolution { public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } class Pancake implements Comparable { final int r; final int h; public Pancake(int r, int h) { this.r = r; this.h = h; } @Override public int compareTo(Pancake o) { int t = -Integer.compare(r, o.r); if (t != 0) { return t; } return Integer.compare(h, o.h); } double sides() { return 2 * Math.PI * r * h; } double area() { return Math.PI * r * r; } double total() { return sides() + area(); } @Override public String toString() { return "Pancake{" + "r=" + r + ", h=" + h + '}'; } } @Override public void solve(int testNumber) { int n = in.nextInt(); int k = in.nextInt(); List pancakes = new ArrayList<>(); Random random = new Random(); for (int i = 0; i < n; i++) { pancakes.add(new Pancake(in.nextInt(), in.nextInt())); // pancakes.add(new Pancake(random.nextInt(100000), random.nextInt(100000))); } Collections.sort(pancakes); double[][] dp = new double[n + 1][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dp[i][j] = -1; } } // for (Pancake pancake : pancakes) { // System.out.println(pancake); // } Arrays.fill(dp[0], 0); for (int addI = 0; addI < n; addI++) { Pancake add = pancakes.get(addI); double addTotal = add.total(); double addArea = add.area(); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < n; j++) { if (dp[i][j] < 0) { continue; } double newRes = dp[i][j] + addTotal; if (i != 0) { newRes -= addArea; } if (newRes > dp[i + 1][addI]) { // System.out.println("set " + (i + 1) + " " + j + " + " + addI + " = " + newRes); dp[i + 1][addI] = newRes; } } } } double max = -1; for (int i = 0; i < n; i++) { max = Math.max(max, dp[k][i]); } // System.out.println(); out.println(max); } }