Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- inline int readChar();
- template <class T = long long> inline T readInt();
- template <class T> inline void writeInt( T x, char end = 0 );
- inline void writeChar( int x );
- inline void writeWord( const char *s );
- /** Read */
- static const int buf_size = 4096;
- inline int getChar() {
- static char buf[buf_size];
- static int len = 0, pos = 0;
- if (pos == len)
- pos = 0, len = fread(buf, 1, buf_size, stdin);
- if (pos == len)
- return -1;
- return buf[pos++];
- }
- inline int readChar() {
- int c = getChar();
- while (c <= 32)
- c = getChar();
- return c;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getChar();
- return s == 1 ? x : -x;
- }
- const int MAX_MEM = 1e7 * 3;
- int mpos = 0;
- char mem[MAX_MEM];
- inline void * operator new ( size_t n ) {
- char *res = mem + mpos;
- mpos += n;
- assert(mpos <= MAX_MEM);
- return (void *)res;
- }
- inline void operator delete ( void * ) { } // обязательно!
- //inline void * operator new [] ( size_t ) { assert(0); }
- //inline void operator delete [] ( void * ) { assert(0); }
- int r = 1;
- int rnd()
- {
- r = (r + 1791791) % (int)(1e9 + 7);
- return r;
- }
- struct treap
- {
- int y, price;
- long long num;
- long long a_num, profit;
- treap *l, *r;
- treap(int a, int b)
- {
- y = rnd();
- price = a;
- num = b;
- a_num = num;
- profit = price * num;
- l = 0;
- r = 0;
- }
- };
- long long get_anum(treap *t)
- {
- if (!t)
- return 0;
- return t->a_num;
- }
- long long get_pr(treap *t)
- {
- if (!t)
- return 0;
- return t->profit;
- }
- void recalc(treap *t)
- {
- if (t != 0)
- {
- t->a_num = get_anum(t->l) + t->num + get_anum(t->r);
- t->profit = get_pr(t->l) + t->num * t->price + get_pr(t->r);
- }
- }
- treap* merge(treap *a, treap *b)
- {
- if (!a)
- return b;
- if (!b)
- return a;
- treap *res;
- if (a->y > b->y)
- {
- a->r = merge(a->r, b);
- res = a;
- }
- else
- {
- b->l = merge(a, b->l);
- res = b;
- }
- recalc(res);
- return res;
- }
- treap** split(treap *a, long long k)
- {
- if (!a)
- return new treap*[2] {0, 0};
- treap **res;
- if (a->price > k)
- {
- res = split(a->l, k);
- a->l = res[1];
- res[1] = a;
- recalc(res[1]);
- }
- else
- {
- res = split(a->r, k);
- a->r = res[0];
- res[0] = a;
- recalc(res[0]);
- }
- return res;
- }
- struct my
- {
- long long place;
- long long num, price;
- };
- int main() {
- long long n = readInt(), m=readInt(), p = readInt();
- pair<long long, long long> fish[n];
- my shop[m];
- for (int i = 0; i < n; i++)
- fish[i].first = readInt(), fish[i].second = readInt();
- for (int i = 0; i < m; i++)
- shop[i].place = readInt(), shop[i].num=readInt(), shop[i].price = readInt();
- //cin >> shop[i].place >> shop[i].num >> shop[i].price;
- treap *root = 0;
- int i = 0, j = 0;
- long long caught = 0;
- long long res = 0;
- while (i < n || j < m)
- {
- long long place;
- if (j == m || (i < n && fish[i].first < shop[j].place))
- {
- place = fish[i].first;
- caught += fish[i].second;
- i++;
- }
- else
- {
- auto ins = new treap(shop[j].price, shop[j].num);
- place = shop[j].place;
- j++;
- auto t1 = split(root, ins->price);
- t1[0] = merge(t1[0], ins);
- root = merge(t1[0], t1[1]);
- }
- long long to_sell = caught;
- long long curr = -place * p;
- auto our = root;
- while (our && to_sell > 0)
- {
- if (our->a_num <= to_sell)
- {
- curr += our->profit;
- to_sell = 0;
- }
- else if (get_anum(our->r) >= to_sell)
- our = our->r;
- else
- {
- to_sell -= get_anum(our->r);
- curr += get_pr(our->r);
- curr += min(to_sell, (long long)our->num) * our->price;
- to_sell -= min(to_sell, (long long)our->num);
- if (to_sell > 0)
- our = our->l;
- }
- }
- res = max(res, curr);
- }
- cout << res;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement