oj.uz

Submission #163205

# Submission time Handle Problem Language Result Execution time Memory
163205 2019-11-11T18:08:24 Z TadijaSebez 코알라 (JOI13_koala) C++11
100 / 100
 151 ms 7532 KB 
#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

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]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 4360 KB Output is correct
2 Correct 62 ms 4056 KB Output is correct
3 Correct 27 ms 2932 KB Output is correct
4 Correct 59 ms 4336 KB Output is correct
5 Correct 36 ms 2804 KB Output is correct
6 Correct 25 ms 1776 KB Output is correct
7 Correct 32 ms 3440 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6324 KB Output is correct
2 Correct 151 ms 7300 KB Output is correct
3 Correct 129 ms 7532 KB Output is correct
4 Correct 113 ms 7508 KB Output is correct
5 Correct 91 ms 4852 KB Output is correct
6 Correct 64 ms 3572 KB Output is correct