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
74
75
76
77
78
79
80
81
82
/*****************************************************************************
* ZADANIE : Siano (runda 1A)                                                 *
* AUTOR   : Lukasz Kierat                                                    *
*****************************************************************************/
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  long long i, b, d, d1, n, m, val;
  vector<long long> rate(500001, 0), height(500001, 0);

  scanf ("%lld%lld", &n, &m);
  for (i = 0; i < n; ++i)
    scanf ("%lld", &rate[i]);
  sort (rate.begin(), rate.begin() + n);
  d1 = 0;
  while (m--) {
    scanf ("%lld%lld", &d, &b);
    for (i = val = 0; i < n; ++i) {
      height[i] += rate[i] * (d - d1);
      if (height[i] > b) {
        val += height[i] - b;
        height[i] = b;
      }
    }
    d1 = d;
    printf ("%lld\n", val);
  }

  return 0;
}
/*#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

long long D, b1;

int main()
{
  long long i, b, d, n, m, d1, val;
  vector<long long> rate(500001), sum(500001);
  vector<long long>::iterator it;

  scanf ("%lld%lld", &n, &m);
  for (i = 0; i < n; ++i)
    scanf ("%lld", &rate[i]);
  sort (rate.begin(), rate.begin() + n);
  for (i = n - 2, sum[n - 1] = rate[n - 1]; i >= 0; --i)
    sum[i] = rate[i] + sum[i + 1];
  d1 = b1 = 0;
  
  for (i = 0; i < n; ++i)
    printf ("%lld ", rate[i]);
  putchar ('\n');
  for (i = 0; i < n; ++i)
    printf ("%lld ", sum[i]);
  putchar ('\n');
  val = 0;
  while (m--) {
    scanf ("%lld%lld", &d, &b);
    D = (d);
    it = upper_bound (rate.begin(), rate.begin() + n, b,
         [](const long long &x, const long long &y) {return x < y * D;} ); 
    printf ("upper_bound_id=%d, D=%lld, d=%lld, d1=%lld, b=%lld, b1=%lld **", 
    it - rate.begin(), D, d, d1, b, b1);
    if (D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val > 0) {
    printf ("%lld\n",
    D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val);
    val += D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val;
    }
    else printf ("0\n");
    d1 = d; b1 = b;
  }

  return 0;
}*/