Submission #24924

#	Time	Username	Problem	Language	Result	Execution time	Memory
24924		tlwpdus	코알라 (JOI13_koala)	C++14	100 / 100	166 ms	11664 KiB

koala

    #include <bits/stdc++.h>

    using namespace std;
     
    typedef long long ll;
     
    ll tree[530000], d, a, n;
    ll b[100100], t[100100];
    int key = 262144;
     
    void upd(int s, int e, ll val) {
        s+=key;e+=key;
        while(s<=e) {
            if (s%2==1) tree[s] = max(tree[s],val);
            if (e%2==0) tree[e] = max(tree[e],val);
            s = (s+1)>>1; e = (e-1)>>1;
        }
    }
     
    ll getv(int idx) {
        ll maxi = -(1LL<<50);
        idx+=key;
        while(idx>0) {
            maxi = max(maxi,tree[idx]);
            idx>>=1;
        }
        return maxi;
    }
     
    vector<ll> comp;
    void com(ll t[]) {
        int i;
        for (i=0;i<n;i++) {
            comp.push_back(t[i]%d);
            comp.push_back((t[i]+1)%d);
        }
        comp.push_back(d);
        sort(comp.begin(),comp.end());
        comp.erase(unique(comp.begin(),comp.end()),comp.end());
    }
     
    ll mokx(ll a, ll b) {
        if (a>0) return (a-1)/b+1;
        return a/b;
    }
     
    int loc(ll val) {
        return lower_bound(comp.begin(),comp.end(),val)-comp.begin();
    }
     
    ll f[100100];
    void solve() {
        int i;
        upd(loc(0),loc(0),0);
        upd(loc(1),loc(d),-a);
        for (i=1;i<n;i++) {
            f[i] = getv(loc(t[i]%d))-(t[i]/d)*a+b[i];
            upd(loc(0),loc(t[i]%d),-(mokx(-t[i],d)*a)+f[i]);
            upd(loc((t[i]+1)%d),loc(d),-(mokx(d-t[i],d)*a)+f[i]);
        }
        printf("%lld\n",f[n-1]);
    }
     
    int main() {
        ll kt, mt;
        int i;
     
        for (i=1;i<key*2;i++) tree[i] = -(1LL<<50);
        scanf("%lld%lld%lld%lld%lld",&kt,&mt,&d,&a,&n);
        t[0] = 0; t[n+1] = mt-kt;
        for (i=1;i<=n;i++) {
            scanf("%lld%lld",&t[i],&b[i]);
            t[i]-=kt;
        }
        n+=2;
        com(t);
        solve();
     
        return 0;
    }

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:69:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld%lld%lld",&kt,&mt,&d,&a,&n);
                                                       ^
koala.cpp:72:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld%lld",&t[i],&b[i]);
                                          ^

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