import java.io.BufferedInputStream; import java.io.IOException; import java.io.InputStream; import java.util.Arrays; public class sia { private static InputStream in; public static void main(String[] args) throws IOException { in = new BufferedInputStream(System.in); int n = (int) nextLong(); int m = (int) nextLong(); int[] a = new int[n]; long[] crops = new long[n]; for (int i = 0; i < n; i++) { a[i] = (int) nextLong(); } Arrays.sort(a); long d, b; long previousDay = 0; long delta; long harvest; for (int i = 0; i < m; i++) { d = nextLong(); delta = d - previousDay; b = nextLong(); harvest = 0; for (int j = n - 1; j >= 0; j--) { crops[j] += a[j] * delta; } for (int j = n - 1; j >= 0; j--) { if (crops[j] >= b) { harvest += crops[j] - b; crops[j] = b; } else { break; } } previousDay = d; System.out.println(harvest); } } private static long nextLong() throws IOException { long ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1; ) { if (c >= 48 && c <= 57) { dig = true; ret = ret * 10 + c - 48; } else if (dig) break; } return ret; } }
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 | import java.io.BufferedInputStream; import java.io.IOException; import java.io.InputStream; import java.util.Arrays; public class sia { private static InputStream in; public static void main(String[] args) throws IOException { in = new BufferedInputStream(System.in); int n = (int) nextLong(); int m = (int) nextLong(); int[] a = new int[n]; long[] crops = new long[n]; for (int i = 0; i < n; i++) { a[i] = (int) nextLong(); } Arrays.sort(a); long d, b; long previousDay = 0; long delta; long harvest; for (int i = 0; i < m; i++) { d = nextLong(); delta = d - previousDay; b = nextLong(); harvest = 0; for (int j = n - 1; j >= 0; j--) { crops[j] += a[j] * delta; } for (int j = n - 1; j >= 0; j--) { if (crops[j] >= b) { harvest += crops[j] - b; crops[j] = b; } else { break; } } previousDay = d; System.out.println(harvest); } } private static long nextLong() throws IOException { long ret = 0; boolean dig = false; for (int c = 0; (c = in.read()) != -1; ) { if (c >= 48 && c <= 57) { dig = true; ret = ret * 10 + c - 48; } else if (dig) break; } return ret; } } |