제출 #361367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361367		Dymo	코알라 (JOI13_koala)	C++14	100 / 100	131 ms	8808 KiB

koala

#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];



}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50