Submission #18469

#TimeUsernameProblemLanguageResultExecution timeMemory
18469choyi0521코알라 (JOI13_koala)C++14
100 / 100
253 ms65484 KiB
#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; int k, m, d, a, n; pair<int, int> p[100000]; struct node{ ll x; node *left, *right; node() :x(-2e18), left(NULL), right(NULL){} }; void update(node *h, int l, int r, int g, ll x){ if (r < g || g < l) return; h->x = max(h->x, x); if (l != r){ if (!h->left) h->left = new node; if (!h->right) h->right = new node; update(h->left, l, (l + r) / 2, g, x); update(h->right, (l + r) / 2 + 1, r, g, x); } } ll query(node *h, int l, int r, int gl, int gr){ if (r < gl || gr < l) return -2e18; if (gl <= l && r <= gr) return h->x; else{ if (!h->left) h->left = new node; if (!h->right) h->right = new node; return max(query(h->left, l, (l + r) / 2, gl, gr), query(h->right, (l + r) / 2 + 1, r, gl, gr)); } } int main(){ scanf("%d %d %d %d %d", &k, &m, &d, &a, &n); for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second); sort(p, p + n); node *rt = new node; update(rt, 0, d - 1, k%d, (ll)k / d*a); for (int i = 0; i < n; i++){ ll maxi = max((ll)-(p[i].first / d + 1)*a + query(rt, 0, d - 1, 0, p[i].first%d - 1), (ll)-p[i].first / d*a + query(rt, 0, d - 1, p[i].first%d, d - 1)) + p[i].second; update(rt, 0, d - 1, p[i].first%d, maxi + (ll)p[i].first / d*a); } printf("%lld", max((ll)-(m / d + 1)*a + query(rt, 0, d - 1, 0, m%d - 1), (ll)-m / d*a + query(rt, 0, d - 1, m%d, d - 1))); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...