fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static class Figure {
  5.         long ki;
  6.         int ci;
  7.  
  8.         public Figure(long ki, int ci) {
  9.             this.ki = ki;
  10.             this.ci = ci;
  11.         }
  12.     }
  13.  
  14.     public static void main(String[] args) {
  15.         Scanner scanner = new Scanner(System.in);
  16.  
  17.         int n = scanner.nextInt();
  18.         List<Figure> figures = new ArrayList<>();
  19.         for (int i = 0; i < n; i++) {
  20.             long ki = scanner.nextLong();
  21.             int ci = scanner.nextInt();
  22.             figures.add(new Figure(ki, ci));
  23.         }
  24.  
  25.         Collections.sort(figures, Comparator.comparingInt(f -> f.ci));
  26.  
  27.         int t = scanner.nextInt();
  28.         long[] p = new long[t];
  29.         for (int i = 0; i < t; i++) {
  30.             p[i] = scanner.nextLong();
  31.         }
  32.  
  33.         long sum = 0;
  34.         int nextPIndex = 0;
  35.         long points = 0;
  36.  
  37.         for (Figure figure : figures) {
  38.             long ki = figure.ki;
  39.             int ci = figure.ci;
  40.  
  41.             while (ki > 0) {
  42.                 if (nextPIndex >= t) {
  43.                     points += ki * (t + 1) * ci;
  44.                     sum += ki;
  45.                     ki = 0;
  46.                 } else {
  47.                     while (nextPIndex < t && p[nextPIndex] <= sum) {
  48.                         nextPIndex++;
  49.                     }
  50.  
  51.                     if (nextPIndex >= t) {
  52.                         points += ki * (t + 1) * ci;
  53.                         sum += ki;
  54.                         ki = 0;
  55.                     } else {
  56.                         long currentP = p[nextPIndex];
  57.                         long available = currentP - sum;
  58.                         if (available <= 0) {
  59.                             nextPIndex++;
  60.                             continue;
  61.                         }
  62.                         long m = Math.min(available, ki);
  63.                         int currentFactor = nextPIndex + 1;
  64.                         points += m * currentFactor * ci;
  65.                         sum += m;
  66.                         ki -= m;
  67.                         if (sum >= currentP) {
  68.                             nextPIndex++;
  69.                         }
  70.                     }
  71.                 }
  72.             }
  73.         }
  74.  
  75.         System.out.println(points);
  76.     }
  77. }
Success #stdin #stdout 0.14s 56672KB
comments (?)
stdin
copy 
1
5 10
2
3 6
stdout
copy 
70
https://ideone.com/UmhgpK
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!