首页 > 代码库 > hdu 1355 The Peanuts

hdu 1355 The Peanuts

http://acm.hdu.edu.cn/showproblem.php?pid=1355

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #define maxn 10000 6 using namespace std; 7  8 struct node 9 {10     int x,y,w;11     bool operator <(const node &a)const12     {13         return w>a.w;14     }15 }p[maxn];16 int n,m,k;17 18 int main()19 {20     int t;21     scanf("%d",&t);22     while(t--)23     {24         scanf("%d%d%d",&n,&m,&k);25         int cnt=0;26         for(int i=1; i<=n; i++)27         {28             for(int j=1; j<=m; j++)29             {30                 int xx;31                 scanf("%d",&xx);32                 if(xx)33                 {34                   p[cnt].x=i;35                   p[cnt].y=j;36                   p[cnt++].w=xx;37                 }38             }39         }40         sort(p,p+cnt);41         __int64 sum=0,ans=0;42         for(int i=0; i<cnt; i++)43         {44             if(i==0)45             {46                 sum+=p[i].x;47             }48             else sum+=abs(p[i].x-p[i-1].x)+abs(p[i].y-p[i-1].y);49             if(sum+p[i].x+1<=k)50             {51                 ans+=p[i].w;52                 sum++;53             }54             else break;55         }56         cout<<ans<<endl;57     }58     return 0;59 }
View Code