Submission #1191449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191449		vnedu	코알라 (JOI13_koala)	C++17	100 / 100	42 ms	4036 KiB

koala

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e5 + 10;
int k,m,d,a,n,t[N],b[N];
ll dp[N];
namespace sub1
{
    bool check()
    {
        return (n<=1000);
    }
    const ll inf = 3e18;
    void solve()
    {
        t[0]=k,b[0]=0;
        t[n+1]=m,b[n+1]=0;
        for(int i=1;i<=n+1;++i)
        {
            dp[i]=-inf;
            for(int j=0;j<i;++j) maximize(dp[i],-((t[i]-t[j]+d-1)/d*1LL*a)+dp[j]+b[i]);
//            cout<<i<<' '<<dp[i]<<'\n';
        }
        cout<<dp[n+1];
    }
}
namespace subfull
{
    const ll inf = 3e18;
    vector<int> nen;
    int sz;
    ll bit[2][N];
    void update(bool id, int x, ll val)
    {
        if(id==1) x=sz-x+1;
        while(x<=sz)
        {
            maximize(bit[id][x],val);
            x+=x&-x;
        }
    }
    ll get(bool id, int x)
    {
        if(id==1) x=sz-x+1;
        ll ans=-inf;
        while(x>=1)
        {
            maximize(ans,bit[id][x]);
            x-=x&-x;
        }
        return ans;
    }
    void updateDp(int i)
    {
        int x=lower_bound(all(nen),t[i]%d)-nen.begin()+1;
        update(0,x,dp[i]+t[i]/d*1LL*a);
        update(1,x,dp[i]+t[i]/d*1LL*a);
    }
    void solve()
    {
        t[0]=k,b[0]=0;
        t[n+1]=m,b[n+1]=0;
        for(int i=0;i<=n+1;++i) nen.pb(t[i]%d);
        sort(all(nen)); nen.erase(unique(all(nen)),nen.end());
        sz=(int)nen.size();
        for(int i=0;i<N;++i) bit[0][i]=bit[1][i]=-inf;
        updateDp(0);
        for(int i=1;i<=n+1;++i)
        {
            dp[i]=-inf;
            int x=lower_bound(all(nen),t[i]%d)-nen.begin()+1;
//            cout<<x<<' ';
            maximize(dp[i],get(0,x-1)-a);
            maximize(dp[i],get(1,x));
            dp[i]+=b[i]-(t[i]/d*1LL*a);
            updateDp(i);
//            cout<<i<<' '<<dp[i]<<'\n';
        }
        cout<<dp[n+1];
    }
}
void solve()
{
    cin>>k>>m>>d>>a>>n;
    for(int i=1;i<=n;++i) cin>>t[i]>>b[i];
    if(sub1::check()) return void(sub1::solve());
    return void(subfull::solve());
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

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