Codeforces 446B DZY Loves Modification

题目链接~~>

解题思路：

                首先，要把行列分开处理，假设选择 i 次行 , k - i 次列 ，如果先选行 ，那么当选择列时每选择一次列就减去 i*p ,选择 k - i 次列就减去 i * (k - i ) * p ,所以我们可以先单独处理行，然后单独处理列，最后只要减去 i * (k - i ) * p 即可。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const INT INF = 9999999 ;
     
    
   

    

     

    
    

     

      const INT mod = 1e9 + 7 ;
     
    
   

    

     

    
    

     

      const INT MY = 200 + 10 ;
     
    
   

    

     

    
    

     

      const INT MX = 1000 + 10 ;
     
    
   

    

     

    
    

     

      INT n ,m , p ,k ;
     
    
   

    

     

    
    

     

      priority_queue<INT>row ,col ;
     
    
   

    

     

    
    

     

      INT a[MX] ,b[MX] ,R[MX*MX] ,L[MX*MX] ;
     
    
   

    

     

    
    

     

      void input()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

         INT x ;
     
    
   

    

     

    
    

     
   memset(a ,0 ,sizeof(a)) ;
     
    
   

    

     

    
    

     
   memset(b ,0 ,sizeof(b)) ;
     
    
   

    

     

    
    

     
   for(INT i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 for(INT j = 0 ;j < m ; ++j)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%I64d" ,&x) ;
     
    
   

    

     

    
    

     

       a[i] += x ;
     
    
   

    

     

    
    

     

       b[j] += x ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
   while(!row.empty())
     
    
   

    

     

    
    

     

       row.pop() ;
     
    
   

    

     

    
    

     
   while(!col.empty())
     
    
   

    

     

    
    

     

       col.pop() ;
     
    
   

    

     

    
    

     
   for(INT i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     

       row.push(a[i]) ;
     
    
   

    

     

    
    

     
   for(INT i = 0 ;i < m ; ++i)
     
    
   

    

     

    
    

     

       col.push(b[i]) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void solve()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT temp ;
     
    
   

    

     

    
    

     
 memset(R ,0 ,sizeof(R)) ;
     
    
   

    

     

    
    

     
 memset(L ,0 ,sizeof(L)) ;
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= k ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       temp = row.top() ;
     
    
   

    

     

    
    

     

       row.pop() ;
     
    
   

    

     

    
    

     

       R[i] += temp + R[i-1] ;
     
    
   

    

     

    
    

     

       row.push(temp - p*m) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= k ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       temp = col.top() ;
     
    
   

    

     

    
    

     

       col.pop() ;
     
    
   

    

     

    
    

     

       L[i] += temp + L[i-1] ;
     
    
   

    

     

    
    

     

       col.push(temp - p*n) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT ans = L[k] ;
     
    
   

    

     

    
    

     
 for(INT i = 1 ;i <= k ; ++i)
     
    
   

    

     

    
    

     

       ans = max(ans ,R[i] + L[k-i] - i*(k-i)*p) ;
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 while(~scanf("%I64d%I64d%I64d%I64d" ,&n ,&m ,&k ,&p))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       input() ;
     
    
   

    

     

    
    

     

       solve() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/38816387