# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
203013 | arnold518 | 코알라 (JOI13_koala) | C++14 | 53 ms | 8824 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const ll INF = 1e18;
int N;
ll S, E, D, A;
ll T[MAXN+10], B[MAXN+10];
ll dp[MAXN+10];
struct BIT
{
ll tree[MAXN+10];
BIT() { for(int i=0; i<MAXN+10; i++) tree[i]=-INF; }
void update(ll i, ll x) { for(; i<=D; i+=(i&-i)) tree[i]=max(tree[i], x); }
ll query(ll i) { ll ret=-INF; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; }
}bitl, bitr;
int main()
{
int i, j;
scanf("%lld%lld%lld%lld%d", &S, &E, &D, &A, &N);
for(i=1; i<=N; i++) scanf("%lld%lld", &T[i], &B[i]);
T[0]=S; T[N+1]=E;
for(i=0; i<=N+1; i++)
{
if(i) dp[i]=max(bitl.query(T[i]%D)-A, bitr.query(D-T[i]%D))+B[i]-A*(T[i]/D);
else dp[i]=0;
bitl.update(T[i]%D+1, dp[i]+A*(T[i]/D));
bitr.update(D-T[i]%D, dp[i]+A*(T[i]/D));
}
printf("%lld\n", dp[N+1]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |