codeforces#FF(div2) D DZY Loves Modification-白红宇

codeforces#FF(div2) D DZY Loves Modification

阅读量：7226 次

发布时间：2019-06-29

本文共 2279 字，大约阅读时间需要 7 分钟。

首先要知道选择行列操作时顺序是无关的

用两个数组row[i],col[j]分别表示仅选择i行能得到的最大值和仅选择j列能得到的最大值

这个用优先队列维护，没选择一行(列)后将这行(列)的和减去对应的np (mp)又一次增加队列

枚举选择行的次数为i,那么选择列的次数为k - i次，ans = row[i] + col[k - i] - (k - i) * i * p;

既然顺序无关，能够看做先选择完i次行，那么每次选择一列时都要减去i * p，选择k - i次列，即减去(k - i) * i * p

//#pragma comment(linker, "/STACK:102400000,102400000")//HEAD#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 using namespace std;//LOOP#define FE(i, a, b) for(int i = (a); i <= (b); ++i)#define FED(i, b, a) for(int i = (b); i>= (a); --i)#define REP(i, N) for(int i = 0; i < (N); ++i)#define CLR(A,value) memset(A,value,sizeof(A))//STL#define PB push_back//INPUT#define RI(n) scanf("%d", &n)#define RII(n, m) scanf("%d%d", &n, &m)#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)#define RS(s) scanf("%s", s)#define FF(i, a, b) for(int i = (a); i < (b); ++i)#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)#define CPY(a, b) memcpy(a, b, sizeof(a))#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)#define ALL(c) (c).begin(), (c).end()#define SZ(V) (int)V.size()#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)#define WI(n) printf("%d\n", n)#define WS(s) printf("%s\n", s)#define sqr(x) x * xtypedef vector 
                 
                   VI;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const int maxn = 1010;const double eps = 1e-10;const LL MOD = 1e9 + 7;int ipt[maxn][maxn];LL row[maxn * maxn], col[maxn * maxn];LL rtol[maxn], ctol[maxn];int main(){ int n, m, k, p; while (~RIV(n, m, k, p)) { priority_queue
                  
                    r, c; int radd = 0, cadd = 0; CLR(rtol, 0), CLR(ctol, 0); FE(i, 1, n) FE(j, 1, m) { RI(ipt[i][j]); rtol[i] += ipt[i][j]; ctol[j] += ipt[i][j]; } FE(i, 1, n) r.push(rtol[i]); FE(j, 1, m) c.push(ctol[j]); row[0] = 0, col[0] = 0; FE(i, 1, k) { LL x = r.top(), y = c.top(); r.pop(), c.pop(); r.push(x - m * p); c.push(y - n * p); row[i] = row[i - 1] + x; col[i] = col[i - 1] + y; }// FE(i, 0, k)// cout << row[i] + col[k - i] <