Submission #361273

#	Time	Username	Problem	Language	Result	Execution time	Memory
361273		Killer2501	코알라 (JOI13_koala)	C++14	100 / 100	133 ms	9976 KiB

koala

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "talltree"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
const ll mod = 1e15+7;
const ll N = 2e5+5;
vector<ll> adj[N];
vector<ll> kq;
vector<pll> pre;
ll n, m, t, k, b[N], p, a[N], ans, tong, d[N], st[N*4], K, D, M, A;
void build(ll id, ll l, ll r)
{
    st[id] = -mod;
    if(l == r)
    {
        return;
    }
    ll mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
    if(u <= l && r <= v)return st[id];
    if(u > r || l > v || u > v)return -mod;
    ll mid = (l + r) / 2;
    return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
void update(ll id, ll l, ll r, ll u, ll v)
{
    if(l == r)
    {
        st[id] = max(st[id], v);
        return;
    }
    ll mid = (l + r) / 2;
    if(mid >= u)update(id*2, l, mid, u, v);
    else update(id*2+1, mid+1, r, u, v);
    st[id] = max(st[id*2], st[id*2+1]);
}
ll findp(ll u)
{
    return lower_bound(kq.begin(), kq.end(), u) - kq.begin() + 1;
}
void sol()
{
    cin >> K >> M >> D >> A >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i] >> b[i];
        kq.pb(a[i]%D);
    }
    kq.pb(K%D);
    kq.pb(M%D);
    sort(kq.begin(), kq.end());
    kq.erase(unique(kq.begin(), kq.end()), kq.end());
    build(1, 1, n+2);
    k = (K / D) * A;
    update(1, 1, n+2, findp(K%D), k);
    for(int i = 1; i <= n; i ++)
    {
        //cin >> a[i] >> b[i];
        k = findp(a[i] % D);
        m = max(get(1, 1, n+2, 1, k-1)-A, get(1, 1, n+2, k, n+2));
        m += -(a[i] / D) * A + b[i];
        //cout << m<<'\n';
        update(1, 1, n+2, k, m + (a[i] / D) * A );
    }
    k = findp(M % D);
    t = -(M / D) * A;
    cout << t + max(get(1, 1, n+2, 1, k-1)-A, get(1, 1, n+2, k, n+2));
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:82:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   82 |        freopen(task".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:83:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   83 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50