fork download
copy 
  1. // Kỹ thuật sử dụng: Quy hoạch động+Tìm kiếm nhị phân
  2. #include<bits/stdc++.h>
  3. #define faster ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. using namespace std;
  6. ll n,m,k,res;
  7. pair<ll,ll> toado[1002];
  8. void tkiem(ll p,ll &a,pair<ll,ll> &b,pair<ll,ll> &c, ll &d,const map<ll,ll> &pos)
  9. {
  10. 	c=*pos.upper_bound(p);
  11. 	if(c.first<n+1) d=(pos.upper_bound(c.first))->first;
  12. 	b=*(--pos.lower_bound(p));
  13. 	if(b.first>0) a=(--pos.lower_bound(b.first))->first;
  14. }
  15. void in(ll p,map<ll,ll> &pos,set<pair<ll,ll>,greater<pair<ll,ll>>> &s)
  16. {
  17. 	ll d=n+10,a=-1,res=++pos[p];
  18. 	pair<ll,ll> c={0,0},b={0,0};
  19. 	tkiem(p,a,b,c,d,pos);
  20. 	if(res>1)
  21. 	{
  22. 		s.erase({c.first-b.first-1,b.first});
  23. 		return;
  24. 	}
  25. 	if(a>-1&&b.second==1)
  26. 	{
  27. 		s.erase({c.first-a-1,a});
  28. 		s.insert({p-a-1,a});
  29. 	}
  30. 	if(d<n+10&&c.second==1)
  31. 	{
  32. 		s.erase({d-b.first-1,b.first});
  33. 		s.insert({d-p-1,p});
  34. 	}
  35. 	s.insert({c.first-b.first-1,b.first});
  36. }
  37. int main()
  38. {
  39. 	faster
  40. 	ll i,r1,r2,r,c,ma,j;
  41. 	cin>>m>>n>>k;
  42. 	for(i=1;i<=k;i++)
  43. 	{
  44. 		cin>>r>>c;
  45. 		toado[i]={r,c};
  46. 	}
  47. 	sort(toado+1,toado+k+1);
  48. 	toado[k+1]={m+1,0};
  49. 	for(i=1;i<=k;i++)
  50. 	{
  51. 		if(toado[i].first>toado[i-1].first)
  52. 		{
  53. 			r1=-1;
  54. 			if(toado[i].first>toado[i-1].first) r1=toado[i-1].first+1;
  55. 			map<ll,ll> pos;
  56. 			set<pair<ll,ll>,greater<pair<ll,ll>>> s;
  57. 			ma=0;
  58. 			pos.insert({0,1});
  59. 			pos.insert({n+1,1});
  60. 			for(j=i;j<=k+1;j++)
  61. 			{
  62. 				if(toado[j].first>toado[j-1].first)
  63. 				{
  64. 					if(j>1)
  65. 					{
  66. 						r2=toado[j].first-1;
  67. 						ma=(s.begin())->first;
  68. 						res=max(res,(r2-r1+1)*ma);
  69. 						if(j<=k) in(toado[j].second,pos,s);
  70. 					}
  71. 					else
  72. 					{
  73. 						pos[toado[j].second]=1;
  74. 						s.insert({n,0});
  75. 					}
  76. 				}
  77. 				else in(toado[j].second,pos,s);
  78. 			}
  79. 		}
  80. 	}
  81. 	cout<<res;
  82. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4 5 4
2 3
2 5
3 1
4 4
stdout
copy 
9
https://ideone.com/xZpyaO
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!