oj.uz

Submission #24924

# Submission time Handle Problem Language Result Execution time Memory
24924 2017-06-17T07:41:26 Z tlwpdus 코알라 (JOI13_koala) C++14
100 / 100
 166 ms 11664 KB 
    #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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8508 KB Output is correct
2 Correct 0 ms 8508 KB Output is correct
3 Correct 3 ms 8508 KB Output is correct
4 Correct 0 ms 8508 KB Output is correct
5 Correct 0 ms 8508 KB Output is correct
6 Correct 0 ms 8508 KB Output is correct
7 Correct 0 ms 8508 KB Output is correct
8 Correct 3 ms 8508 KB Output is correct
9 Correct 0 ms 8508 KB Output is correct
10 Correct 0 ms 8508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 11664 KB Output is correct
2 Correct 66 ms 11664 KB Output is correct
3 Correct 33 ms 10128 KB Output is correct
4 Correct 59 ms 11664 KB Output is correct
5 Correct 53 ms 10128 KB Output is correct
6 Correct 36 ms 10128 KB Output is correct
7 Correct 36 ms 11664 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 11664 KB Output is correct
2 Correct 166 ms 11664 KB Output is correct
3 Correct 133 ms 11664 KB Output is correct
4 Correct 126 ms 11664 KB Output is correct
5 Correct 113 ms 10128 KB Output is correct
6 Correct 66 ms 10128 KB Output is correct