import java.util.Arrays; import java.util.Scanner; /** * Created by lpalonek on 29/09/15. */ class sia { public static void main(String args[]) { Scanner keyboard = new Scanner(System.in); int area = keyboard.nextInt(); int mowNumber = keyboard.nextInt(); long[] growthRate = new long[area]; long growth = 0; long growthMin = -1; for (int i = 0; i < area; i++) { growthRate[i] = keyboard.nextLong(); growth += growthRate[i]; if (growthMin > growthRate[i] || growthMin < 0) { growthMin = growthRate[i]; } } Arrays.sort(growthRate); long prevDay = 0; long prevMowingHeight = 0; long sum = 0; long diff = 0; for (int i = 0; i < mowNumber; i++) { long day = keyboard.nextLong(); long mowingHeight = keyboard.nextLong(); // long sum = 0; long growFactor = mowingHeight - prevMowingHeight; // long growFactor = Math.abs(mowingHeight - prevMowingHeight); long dayFactor = day - prevDay; if (growFactor < 0) { growFactor = mowingHeight; sum = dayFactor * growth - growFactor * area + prevMowingHeight * area; } else { sum = dayFactor * growth - growFactor * area; } if (growthMin * dayFactor < growFactor && (growFactor != mowingHeight || prevMowingHeight == 0)) { int index = Arrays.binarySearch(growthRate, growFactor / dayFactor); if (index < 0) { index = index * (-1) - 1; } else { index++; } if (index != growthRate.length && growthRate[index] == growthRate[index + 1]) { while (index != growthRate.length && growthRate[index] == growthRate[index + 1]) { ++index; } ++index; } else { if (index != growthRate.length && growthRate[index] != growthRate[index + 1]) { index++; } } for (int j = 0; j < index; j++) { diff += growFactor - growthRate[j] * dayFactor; } sum += diff; } else { sum -= diff; diff = 0; } // prevDay = day; prevMowingHeight = mowingHeight; System.out.println(sum); } } }
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | import java.util.Arrays; import java.util.Scanner; /** * Created by lpalonek on 29/09/15. */ class sia { public static void main(String args[]) { Scanner keyboard = new Scanner(System.in); int area = keyboard.nextInt(); int mowNumber = keyboard.nextInt(); long[] growthRate = new long[area]; long growth = 0; long growthMin = -1; for (int i = 0; i < area; i++) { growthRate[i] = keyboard.nextLong(); growth += growthRate[i]; if (growthMin > growthRate[i] || growthMin < 0) { growthMin = growthRate[i]; } } Arrays.sort(growthRate); long prevDay = 0; long prevMowingHeight = 0; long sum = 0; long diff = 0; for (int i = 0; i < mowNumber; i++) { long day = keyboard.nextLong(); long mowingHeight = keyboard.nextLong(); // long sum = 0; long growFactor = mowingHeight - prevMowingHeight; // long growFactor = Math.abs(mowingHeight - prevMowingHeight); long dayFactor = day - prevDay; if (growFactor < 0) { growFactor = mowingHeight; sum = dayFactor * growth - growFactor * area + prevMowingHeight * area; } else { sum = dayFactor * growth - growFactor * area; } if (growthMin * dayFactor < growFactor && (growFactor != mowingHeight || prevMowingHeight == 0)) { int index = Arrays.binarySearch(growthRate, growFactor / dayFactor); if (index < 0) { index = index * (-1) - 1; } else { index++; } if (index != growthRate.length && growthRate[index] == growthRate[index + 1]) { while (index != growthRate.length && growthRate[index] == growthRate[index + 1]) { ++index; } ++index; } else { if (index != growthRate.length && growthRate[index] != growthRate[index + 1]) { index++; } } for (int j = 0; j < index; j++) { diff += growFactor - growthRate[j] * dayFactor; } sum += diff; } else { sum -= diff; diff = 0; } // prevDay = day; prevMowingHeight = mowingHeight; System.out.println(sum); } } } |