fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define tag "spoj"
  4. #define maxn 1007
  5. #define oo 1000000007
  6. #define mid ((l+r)>>1)
  7. #define meset(a,x) memset(a,x,sizeof(a))
  8. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  9. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  10. class it2D{
  11.  
  12.     struct item{
  13.  
  14.         int id;
  15.         int l,r;
  16.  
  17.         item(const int &i,const int &L,const int &R): id(i), l(L), r(R) {};
  18.  
  19.         item left()
  20.         const{
  21.             return item(id<<1,l,mid);
  22.         }
  23.  
  24.         item right()
  25.         const{
  26.             return item(id<<1|1,mid+1,r);
  27.         }
  28.  
  29.         bool belong(const int &L,const int &R)
  30.         const{
  31.             return L<=l && r<=R;
  32.         }
  33.         bool irrelevent(const int &L,const int &R)
  34.         const{
  35.             return R<l || L>r;
  36.         }
  37.     };
  38.  
  39.     int m,n;
  40.  
  41.     item rtx,rty;
  42.  
  43.     vector<vector<int>> node;
  44.  
  45.     void update(const item &dx,const item &dy,const int &x,const int &y,const int &val,const bool &only_y)
  46.     {
  47.         if(dx.irrelevent(x,x) || dy.irrelevent(y,y)) return;
  48.  
  49.         if(dx.l==dx.r && dy.l==dy.r) return node[dx.id][dy.id]=val,void();
  50.  
  51.         if(dx.l!=dx.r)
  52.         {
  53.             if(!only_y)
  54.                 update(dx.left(),dy,x,y,val,false),
  55.                 update(dx.right(),dy,x,y,val,false);
  56.  
  57.             node[dx.id][dy.id]=max(node[dx.left().id][dy.id],node[dx.right().id][dy.id]);
  58.         }
  59.  
  60.         if(dy.l!=dy.r)
  61.         {
  62.             update(dx,dy.left(),x,y,val,true);
  63.             update(dx,dy.right(),x,y,val,true);
  64.  
  65.             if(dx.l==dx.r)
  66.                 node[dx.id][dy.id]=max(node[dx.id][dy.left().id],node[dx.id][dy.right().id]);
  67.         }
  68.     }
  69.  
  70.     int get(const item &dx,const item &dy,const int &x1,const int &y1,const int &x2,const int &y2)
  71.     {
  72.         if(dx.irrelevent(x1,x2) || dy.irrelevent(y1,y2)) return 0;
  73.  
  74.         if(dx.belong(x1,x2))
  75.             return  dy.belong(y1,y2) ? node[dx.id][dy.id] : max(get(dx,dy.left(),x1,y1,x2,y2),get(dx,dy.right(),x1,y1,x2,y2));
  76.  
  77.         return max(get(dx.left(),dy,x1,y1,x2,y2),get(dx.right(),dy,x1,y1,x2,y2));
  78.     }
  79.  
  80. public:
  81.  
  82.     it2D(const int &M,const int &N): m(M), n(N), rtx(1,1,M), rty(1,1,N), node(vector<vector<int>>(4*M+7,vector<int>(4*N+7))) {};
  83.  
  84.     void update(const int &x,const int &y,const int &val)
  85.     {
  86.         update(rtx,rty,x,y,val,false);
  87.     }
  88.  
  89.     int max_range(const int &x1,const int &y1,const int &x2,const int &y2)
  90.     {
  91.         return get(rtx,rty,x1,y1,x2,y2);
  92.     }
  93. };
  94. int main()
  95. {
  96.     #ifdef dmdd
  97.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  98.     #endif // dmdd
  99.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  100.  
  101.  
  102.     int n,k;
  103.     cin>>n>>k;
  104.     vector<int> x(n+1),y(n+1),z(n+1);
  105.  
  106.     for(int i=1;i<=n;i++) cin>>x[i]>>y[i]>>z[i];
  107.  
  108.     it2D st(2*maxn,2*maxn);
  109.  
  110.     #define krange(x,y) x+y-k,x-y-k+maxn,x+y+k,x-y+k+maxn
  111.     for(int i=n,cur;i>=1;i--)
  112.     {
  113.         cur=st.max_range(krange(x[i],y[i])) + z[i];
  114.  
  115.         st.update(x[i]+y[i],x[i]-y[i]+maxn,cur);
  116.     }
  117.  
  118.     cout<<st.max_range(krange(0,0));
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.06s 257668KB
comments (?)
stdin 
8 4

1 2 2

1 5 9

4 3 3

6 4 4

7 7 8

8 2 5

5 1 6

3 2 7
stdout 
27
https://ideone.com/2LvObk
language:
C++14 (gcc 8.3)
created:
6 years 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!