fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. struct sen{
  5.     long x;
  6.     long y;
  7.     long f;
  8.     long vt;
  9. };
  10. int main()
  11. {
  12.     long n, k;
  13.     cin >> n >> k;
  14.     sen *p1= new sen [n+5];
  15.     sen *p2= new sen[n+5];
  16.     long *luu= new long [n+5];
  17.     long *maxi= new long [100005];
  18.     long *maxj= new long [100005];
  19.     long *vt= new long[100005];
  20.     for(long i=1; i<=n; i++){
  21.         cin >> p1[i].x>> p1[i].y>> p1[i].f;
  22.         maxi[p1[i].x]=0;
  23.         maxj[p1[i].y]=0;
  24.         p1[i].vt=i;
  25.         p2[i]=p1[i];
  26.     }
  27.     sen t=p1[1];
  28.     for(long i=1; i<=n-1; i++){
  29.         for(long j=i+1; j<=n; j++){
  30.             if(p1[i].x>p1[j].x){
  31.                 sen temp=p1[i];
  32.                 p1[i]=p1[j];
  33.                 p1[j]= temp;
  34.             }
  35.             else if(p1[i].x==p1[j].x){
  36.                 if(p1[i].y>p1[j].y){
  37.                     sen temp=p1[i];
  38.                     p1[i]=p1[j];
  39.                     p1[j]= temp;
  40.                 }
  41.             }
  42.             //
  43.             if(p2[i].y>p2[j].y){
  44.                 sen temp=p2[i];
  45.                 p2[i]=p2[j];
  46.                 p2[j]= temp;
  47.             }
  48.             else if(p2[i].y==p2[j].y){
  49.                 if(p2[i].x>p2[j].x){
  50.                     sen temp=p2[i];
  51.                     p2[i]=p2[j];
  52.                     p2[j]= temp;
  53.                 }
  54.             }
  55.         }
  56.     }
  57.     for(long i=1; i<=n; i++){
  58.         vt[p2[i].vt]=i;
  59.     }
  60.     long kq = t.f;
  61.     luu[1]=kq;
  62.     for(int i=2; i<=n; i++){
  63.         long k1;
  64.         if(p1[i].x==p1[i-1].x && luu[p1[i-1].vt]>=k){
  65.             k1=luu[p1[i-1].vt]-k+p1[i].f;
  66.             if(maxi[p1[i].x]<k1) maxi[p1[i].x]=k1;
  67.         }
  68.         else {
  69.             k1=0;
  70.         }
  71.         long k2;
  72.         long x=vt[p1[i].vt];
  73.         if(p2[x].y==p2[x-1].y&& luu[p2[x-1].vt]>=k){
  74.             k2=luu[p2[x-1].vt]-k+p2[x].f;
  75.             if(maxj[p1[i].y]<k1) maxj[p1[i].y]=k2;
  76.         }
  77.         else {
  78.             k2=0;
  79.         }
  80.         k1=maxi[p1[i].x]> k1 ? maxi[p1[i].x]:k1;
  81.         k2=maxj[p1[i].y]> k2 ? maxj[p1[i].y]:k2;
  82.         luu[p1[i].vt]=k1>k2?k1:k2;
  83.     }
  84.     cout << luu[n]<< endl;
  85.     return 0;
  86. }
  87.  
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
9 5
1 1 5
2 1 5
1 3 4
1 5 21
2 3 2
3 3 14
4 1 4
4 4 12
4 5 6
stdout
copy 
0
https://ideone.com/8LfDwC
language:
C++ (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!