首页 > 代码库 > Codeforces Round #FF (Div. 2)
Codeforces Round #FF (Div. 2)
D 题说的是给了一个矩阵 然后又k 次操作每次能把一整行 或者一整列 中的每个元素都减去p 然后 加上减去之前的该行和该列, 傻逼的我有没有做出来, 我们可以知道最后结果横的用了x次 竖的用了y次 那么他们用的先后顺序是没有影响的,然后预处理出 横取1 --- k次的最大值 和 竖取 1---k次的最大值 然后枚举x 相应的进行处理就到了最后的答案
#include <iostream>#include <cstdio>#include <string.h>#include <queue>#include <algorithm>using namespace std;const int maxn = 1005;__int64 Martix[maxn][maxn],n,m,k,p;__int64 R[maxn*1000],C[maxn*1000];__int64 maxv(__int64 a,__int64 b){ return a>b?a:b;}int main(){ priority_queue<__int64>row,cloun; while(scanf("%I64d%I64d%I64d%I64d",&n,&m,&k,&p)==4) { for(int i =0;i<n; ++i) for(int j=0; j<m; ++j) scanf("%I64d",&Martix[i][j]); for(int i= 0; i<n; ++i) { __int64 a=0; for(int j=0; j<m; ++j) a+=Martix[i][j]; row.push(a); } for(int i=0; i<m; ++i) { __int64 a=0; for(int j = 0; j<n; ++j) a += Martix[j][i]; cloun.push(a); } R[0]=0; __int64 ans=0; for(int i=1 ; i<=k; ++i ) { __int64 rt =row.top();row.pop(); ans+=rt; R[i]=ans; rt-=m*p; row.push(rt); } C[0]=0; ans=0; for(int i =1; i<=k; ++i) { __int64 rt =cloun.top();cloun.pop(); ans+=rt; rt-=n*p; C[i]=ans; cloun.push(rt); } ans=-1000000000000000000; for(__int64 i =0; i<=k; ++i) { __int64 t = R[i]+C[k-i]; __int64 e = p*i*(k-i); t =t-e; ans=maxv(ans,t); } printf("%I64d\n",ans); while(!row.empty())row.pop(); while(!cloun.empty())cloun.pop(); } return 0;}
Codeforces Round #FF (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。