oj.uz

Submission #361367

# Submission time Handle Problem Language Result Execution time Memory
361367 2021-01-29T14:03:22 Z Dymo 코알라 (JOI13_koala) C++14
100 / 100
 131 ms 8808 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =1e6+10;
const ll mod=1e9+7;
const ll base=3e18;

ll t[maxn];
ll b[maxn];
ll st[4*maxn];
ll get(ll id,ll left,ll right,ll x,ll y)
{
    if (x>right||y<left) return -base;
    if (x<=left&&y>=right) return st[id];
    ll mid=(left+right)/2;
    return max(get(id*2,left,mid,x,y),get(id*2+1,mid+1, right, x, y));
}
void update(ll id,ll left,ll right,ll x,ll val)
{
    if (x>right||x<left) return;
    if (left==right)
    {
        st[id]=max(st[id],val);
        return ;
    }
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,val);
    update(id*2+1, mid+1, right, x, val);
    st[id]=max(st[id*2],st[id*2+1]);
}
ll dp[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
     ll k, m ,d,  a, n;
      cin>> k>> m>> d>> a>> n;
      vector<ll> vt;
      for (int i=1;i<=n;i++)
      {
         cin>>t[i]>>b[i];
         vt.pb(t[i]%d);
      }
      n++;
      t[n]=m;
      b[n]=0;
      vt.pb(t[n]%d);
      sort(vt.begin(),vt.end());
      ll len=vt.size();
      for (int i=1;i<=4*len;i++)
      {
          st[i]=-base;
      }
      for (int i=1;i<=n;i++)
      {
          dp[i]=-(t[i]-k+d-1)/d*a+b[i];
          ll pos=lower_bound(vt.begin(),vt.end(),t[i]%d)-vt.begin()+1;
          ll h=get(1,1,len,pos,len)-(t[i]/d)*a+b[i];
          ll h1=get(1,1,len,1,pos-1)-(t[i]/d*a)-a+b[i];
          dp[i]=max(dp[i],max(h,h1));
         // cout <<dp[i]<<endl;
          update(1,1,len,pos,dp[i]+t[i]/d*a);
      }
      cout <<dp[n];



}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 8808 KB Output is correct
2 Correct 108 ms 8424 KB Output is correct
3 Correct 35 ms 5888 KB Output is correct
4 Correct 97 ms 8552 KB Output is correct
5 Correct 56 ms 5356 KB Output is correct
6 Correct 34 ms 3436 KB Output is correct
7 Correct 51 ms 7784 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 8732 KB Output is correct
2 Correct 129 ms 8680 KB Output is correct
3 Correct 124 ms 8680 KB Output is correct
4 Correct 104 ms 8680 KB Output is correct
5 Correct 78 ms 5616 KB Output is correct
6 Correct 54 ms 4332 KB Output is correct