Submission #163205

#TimeUsernameProblemLanguageResultExecution timeMemory
163205TadijaSebez코알라 (JOI13_koala)C++11
100 / 100
151 ms7532 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=100050; const int M=2*N; const ll inf=3e18; vector<int> ost; int t[N],b[N]; int l,r,d,a,n; int root,tsz,ls[M],rs[M]; ll mx[M]; void Set(int &c, int ss, int se, int qs, int qe, ll f) { if(qs>qe || qs>se || ss>qe) return; if(!c) c=++tsz,mx[c]=-inf; if(qs<=ss && qe>=se){ mx[c]=max(mx[c],f);return;} int mid=ss+se>>1; Set(ls[c],ss,mid,qs,qe,f); Set(rs[c],mid+1,se,qs,qe,f); } ll Get(int c, int ss, int se, int qi) { if(ss==se) return mx[c]; int mid=ss+se>>1; if(qi<=mid) return max(mx[c],Get(ls[c],ss,mid,qi)); else return max(mx[c],Get(rs[c],mid+1,se,qi)); } int GetO(int x){ return lower_bound(ost.begin(),ost.end(),x%d)-ost.begin()+1;} void Set(int x, ll p) { int j=GetO(x); Set(root,1,ost.size(),j+1,ost.size(),p+(ll)(x/d)*a-a); Set(root,1,ost.size(),1,j,p+(ll)(x/d)*a); } ll dp[N]; int main() { scanf("%i %i %i %i %i",&l,&r,&d,&a,&n); t[0]=l;t[n+1]=r; for(int i=1;i<=n;i++) scanf("%i %i",&t[i],&b[i]); for(int i=0;i<=n+1;i++) ost.pb(t[i]%d); sort(ost.begin(),ost.end());ost.erase(unique(ost.begin(),ost.end()),ost.end()); mx[0]=-inf; Set(l,0); for(int i=1;i<=n+1;i++) { dp[i]=Get(root,1,ost.size(),GetO(t[i]))-(ll)(t[i]/d)*a+b[i]; Set(t[i],dp[i]); } printf("%lld\n",dp[n+1]); return 0; }

Compilation message (stderr)

koala.cpp: In function 'void Set(int&, int, int, int, int, long long int)':
koala.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
koala.cpp: In function 'long long int Get(int, int, int, int)':
koala.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
koala.cpp: In function 'int main()':
koala.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i %i",&l,&r,&d,&a,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:41:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&t[i],&b[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...