Codeforces Round #FF (Div. 2) D. DZY Loves Modification Greedy Priority Queue_html/css_WEB-ITnose

Link: http://codeforces.com/problemset/problem/447/D

Question: An n*m matrix can be operated k times, and each operation room is The numbers in a certain row or column are reduced by p, and the score obtained is the sum of the original numbers in this row or column. Find the highest score obtained after N operations.

Idea: First count the sum of numbers in each row and column.

Among the k operations performed, i operations are performed on rows, and the remaining k-i operations are performed on columns. First, ignore the impact of rows on columns in each operation, and then when calculating columns, it can finally be calculated that the total impact is i*(k-i)*p. Find the highest value selected for each i operation to calculate the highest score, recorded as cn[i], rn[i] (use the priority queue to take the first). For different i, take ans=max(cn[i] rn[k-i]-i*(k-i)*p).

Note that the data will exceed int, and the initial value of ans must be extremely small.

Code:

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<queue>#include<stack>#include<vector>#include<ctype.h>#include<cstdlib>#include<algorithm>#include<string>#define PI acos(-1.0)#define maxntypedef long long ll;using namespace std;long long INF =(1LL << 60);priority_queue < long long > c,r;int main(){    int n,m,k,p,x;    long long y;    scanf("%d%d%d%d",&n,&m,&k,&p);    int col[1005],row[1005];    long long cn[1000005],rn[1000005];    for(int i=0; i<n; i++)        for(int j=0; j<m; j++)        {            scanf("%d",&x);            col[j]+=x;            row[i]+=x;        }    for(int i=0; i<n; i++)        r.push(row[i]);    for(int i=0; i<m; i++)        c.push(col[i]);    cn[0]=rn[0]=0;    for(int i=1; i<=k; i++)    {        y=c.top();        cn[i]=cn[i-1]+y;        c.pop();        c.push(y-n*1LL*p);        y=r.top();        rn[i]=rn[i-1]+y;        r.pop();        r.push(y-m*1LL*p);    }    long long ans=-INF;    for(int i=0; i<=k; i++)        ans=max(ans,cn[i]+rn[k-i]-i*1LL*(k-i)*p);    printf("%I64d\n",ans);    return 0;}