[PA 2026] 堆煎饼 / Stosy naleśników

1

Raoxuanrui01 LV 6 @ 2026-9-22 15:22:14

依旧给题解写注释（scy 的）

#include<bits/stdc++.h>
using namespace std;
int n,m,k,cnt;//cnt从小到大的堆 
struct node{
	vector<long long> pre; //针对每个从小至大的堆的前缀和 
	bool operator <(const node &ano){//贪心，我们在选那些完整的堆时一定是从大到小用的 
		return pre[m]>ano.pre[m];
	}
};
long long dow[300005],ris[300005],val[300005];//dow[i]表示从所有从大到小的堆中选i个的答案，ris[i]即从小到大，val用于读入 
long long pre[300005],suf[300005];
//pre[turn(i,j)]从前i个从小到大的堆中必须选择一堆的前j个，其余堆全选时产生的最小损失
//suf[turn(i,j)]从第i个到第cnt个从小到大的堆中选择其中一堆的前j个时能取得的最大值 
long long full[300005];//full[i]从1到i的所有从小到大的堆的饼大小总和 
vector<node> sum;//所有从小到大的堆 
int turn(int x,int y){//类似哈希，将矩阵拍扁变成数组 
	return (x-1)*m+y;
}
int main(){
	cin>>n>>m>>k;
	priority_queue<long long>q;//从大到小的贪心 
	node empty={vector<long long>(m+1,0LL)};
	empty.pre[m]=5e18;
	sum.push_back(empty);
	for(int i=1;i<=n;i++){
		bool flag=1;//flag=1从小到大 
		for(int j=1;j<=m;j++){
			cin>>val[j];
			flag&=(val[j]>=val[j-1]);
		}
		if(!flag)for(int j=1;j<=m;j++)q.push(val[j]);
		else{
			cnt++;
			node ne;
			ne.pre.push_back({0});
			for(int j=1;j<=m;j++)ne.pre.push_back(ne.pre[j-1]+val[j]);//处理堆内前缀和 
			sum.push_back(ne);
		}
	}
	int rise=0,down=0;//rise和down判断最多能取到哪里 
	for(int i=1;i<=k && q.size();i++){
		auto t=q.top();
		q.pop();
		dow[i]=dow[i-1]+t;
		rise=i;
	}
	for(int i=rise+1;i<=n*m;i++)dow[i]=dow[i-1];//同69行，填充剩余的那些 
	sort(sum.begin(),sum.end());
	for(int i=1;i<=cnt;i++)full[i]=full[i-1]+sum[i].pre[m];
	pre[0]=5e18;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=m;j++){
			pre[turn(i,j)]=min(pre[max(turn(i-1,j),0)],sum[i].pre[m]-sum[i].pre[j]);
		}
	}
	for(int i=cnt;i>=1;i--){
		for(int j=1;j<=m;j++){
			suf[turn(i,j)]=max(suf[min(turn(i+1,j),cnt*m+1)],sum[i].pre[j]);
		}
	}
	//预处理所有前后缀，注意此处实现与scy的略有不同 
	for(int i=1;i<=min(cnt*m,k);i++){
		down=i;
		int ful=i/m,ys=i%m;
		if(!ys)ris[i]=full[ful];
		else ris[i]=max(full[ful]+suf[turn(ful+1,ys)],full[ful+1]-pre[turn(ful+1,ys)]);
		//计算答案，前者取前ful个堆再找一个长为ys的最大前缀，后者取前ful+1个堆再删一个长为m-ys的最小后缀 
	}
	for(int i=down+1;i<=n*m;i++)ris[i]=ris[i-1];
	long long ans=0;
	for(int i=0;i<=k;i++){
		ans=max(ans,dow[i]+ris[k-i]);
	}
	cout<<ans;
	return 0;
}
/*
贪心hack: 
2 3 4
1 5 50
1 10 10

2 3 4
1 1 11
1 10 10
*/

1

Hansang1 LV 9 @ 2026-9-22 15:19:35

对于从上到下非递增的煎饼堆，也就是大的饼都在上面的堆。可以把这些饼都存进一个大根堆里面，每次取最大的。

而对于大的在底下的堆，因为对于一个堆内的价值曲线是递增的，所以有能取的空间就要尽量把这个堆的都取完。

假设最优解里有两摞都只取了部分：

A 摞取了 $x$ 张（ $0<x<m$ ），最后一张是 $a_x$ ，B 摞取了 $y$ 张（ $0<y<m$ ），最后一张是 $b_y$ 。

因为每摞都是非递减的，所以：

A 摞下一张 $a_{x+1} \ge a_x$ A 摞下一张 $a_{x+1} \ge a_x$

考虑调整：A 少取一张、B 多取一张。

若 $b_{y+1} > a_x$ ，则 B 多取、A 少取，总价值增加。

若 $a_{x+1} > b_y$ ，则 A 多取、B 少取，总价值增加。

若两者都不成立，即 $b_{y+1} \le a_x$ 且 $a_{x+1} \le b_y$ ，结合单调性：

$a_x \le a_{x+1} \le b_y \le b_{y+1} \le a_x$ 推出所有值都相等。此时调整不改变总价值。

因此，有两非递减堆未取完时，可以继续调整，直到至少一摞变成整摞或 0 张。

发现两部分拆成两个 dp 比较好处理，同时小顶堆需要后缀最大值和前缀放弃最小值：

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 3e5 + 10;
const LL INF = LLONG_MAX;
int n, m, K;

struct node {
	vector<LL> sum;
	vector<LL> nxt;
} nis[N];   // 小顶堆的总和
 
bool cmp(node na, node nb) {
	return na.sum[m] > nb.sum[m];
}

priority_queue<LL> nds;
LL dpde[N], dpin[N];
LL a[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m >> K;
	
	int ni = 0, dlen = 0;
	for (int i = 0; i < n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[j];
        }

        if (a[1] < a[m]) {  // 顶部小底部大
        	ni ++;
        	nis[ni].sum.resize(m + 1, 0);
        	nis[ni].nxt.resize(m + 1, 0);
        	nis[ni].sum[0] = 0;
        	for (int j = 1; j <= m; j ++) {
	            nis[ni].sum[j] = nis[ni].sum[j - 1] + a[j];
	        }
        } 
		else {   // 顶部大底部小
			for (int j = 1; j <= m; j ++) {
	            nds.push(a[j]);
	            dlen ++;
	        }
        }
    }
    
    memset(dpde, 0, sizeof(dpde));
    for (int i = 1; i <= K; i ++) {
    	if (nds.empty()) {
    		dpde[i] = dpde[i - 1];
		}
		else {
	    	dpde[i] = dpde[i - 1] + nds.top();
	    	nds.pop();
	    }
	}
	
	sort(nis + 1, nis + ni + 1, cmp);
	memset(dpin, 0, sizeof(dpin));
	
	vector<LL> sum_total;
	sum_total.resize(ni + 1, 0);
    for (int i = 1; i <= ni; i++) {
        sum_total[i] = sum_total[i - 1] + nis[i].sum[m];
    }
	
	vector<vector<LL>> suf;
	suf.resize(ni + 2);
	for (int i = 0; i < ni + 2; i++) {
	    suf[i].resize(m + 1, 0);
	}
	
	vector<vector<LL>> pre_min;
	pre_min.resize(ni + 1);
	for (int i = 0; i < ni + 1; i++) {
	    pre_min[i].resize(m + 1, INF);
	}
	
	 // suf[i][r]：从第 i 个摞到第 ni 个摞中，取前 r 张的最大值
    for (int r = 0; r <= m; r ++) suf[ni + 1][r] = 0;
    for (int i = ni; i >= 1; i --) {
        for (int r = 0; r <= m; r ++) {
            suf[i][r] = max(suf[i + 1][r], nis[i].sum[r]);
        }
    }

    // pre_min[i][r]：前 i 个摞中，取前 r 张时，放弃的剩余部分的最小值
    for (int r = 0; r <= m; r ++) pre_min[0][r] = INF;
    for (int i = 1; i <= ni; i ++) {
        for (int r = 0; r <= m; r ++) {
            LL loss = nis[i].sum[m] - nis[i].sum[r];
            pre_min[i][r] = min(pre_min[i - 1][r], loss);
        }
    }

    // 计算 dpin[x]：从非递减摞中取 x 张的最大价值
    int max_x = ni * m;
    for (int x = 0; x <= max_x; x++) {
        if (x % m == 0) {
            dpin[x] = sum_total[x / m];
        } 
		else {
            int q = x / m;
            int r = x % m;
            LL val = 0;
            // 取 q 个整摞，然后从 q+1 开始取一个摞的前 r 张
            if (q < ni) {
                val = max(val, sum_total[q] + suf[q + 1][r]);
            }
            // 取 q+1 个整摞，但其中一个只取前 r 张
            if (q + 1 <= ni) {
                val = max(val, sum_total[q + 1] - pre_min[q + 1][r]);
            }
            dpin[x] = val;
        }
    }
    for (int i = max_x + 1; i <= K; i ++) {
        dpin[i] = dpin[max_x];
    }
	
	LL ans = 0;
	for (int i = 0; i <= K; i ++) {
		ans = max(ans, dpde[i] + dpin[K - i]);
	}
    
	cout << ans << "\n";
	
	return 0;
}

1

Benny LV 10 @ 2026-9-22 15:02:49

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,n1,n2;
vector<ll> a[300010],b[300010],tot[300010];
vector<vector<ll>> st[300010],sti[300010],st2[300010]; 
int bid[300010],lg2[300100];
ll tota[3000010],tots[300010],totb[300010];
struct N{
	ll v,x;
	bool operator<(const N &n1)const{
		return v<n1.v;
	}
}u[300010];
bool cmp(N a,N b){
	return a.v>b.v;
}
ll get(int p,int l,int r){
	if(p<=0||l>r)return 0;
	int d=lg2[r-l+1];
	return max(st[p][l][d],st[p][r-(1<<d)+1][d]);
}
int geti(int p,int l,int r){
	int d=lg2[r-l+1];
	if(st2[p][l][d]>st2[p][r-(1<<d)+1][d])return sti[p][l][d];
	else return sti[p][r-(1<<d)+1][d];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	for(int i=2;i<=300000;i++)lg2[i]=lg2[i>>1]+1;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		vector<ll> v(m+5);
		int fl=0;
		for(int j=1;j<=m;j++){
			cin>>v[j];
			if(j>1&&v[j]>v[j-1])fl=1;
		}
		if(fl){
			a[++n1]=v;
			tot[n1]=v;
		}
		else b[++n2]=v;
	}
	for(int i=1;i<=n2;i++)bid[i]=1;
	priority_queue<N> q;
	for(int i=1;i<=n2;i++)q.push({b[i][1],i});
	for(int _=1;_<=n2*m;_++){
		N t=q.top();
		q.pop();
		totb[_]=t.v;
		if(bid[t.x]<m){
			q.push({b[t.x][++bid[t.x]],t.x}); 
		}
	}
	for(int i=1;i<=n2*m;i++)totb[i]+=totb[i-1]; 
	for(int i=1;i<=m;i++)st[i].resize(n1+5),sti[i].resize(n1+5),st2[i].resize(n1+5);
	
	for(int i=1;i<=n1;i++){
		for(int j=1;j<=m;j++)st[j][i].resize(25),sti[j][i].resize(25),st2[j][i].resize(25);
		for(int j=2;j<=m;j++){
			tot[i][j]+=tot[i][j-1];
		}
		u[i].v=tot[i][m];u[i].x=i;
	}
	sort(u+1,u+1+n1,cmp);
	for(int _i=1;_i<=n1;_i++){
		int i=u[_i].x;
		tots[_i]=tots[_i-1]+tot[i][m];
		for(int j=1;j<=m;j++){
			st[j][_i][0]=tot[i][j];
			st2[j][_i][0]=tot[i][j]-tot[i][m];
			sti[j][_i][0]=_i;
		}
	}
	tots[n1+1]=tots[n1];
	for(int p=1;p<=m;p++){
		for(int i=1;i<=20;i++){
			for(int x=1;x+(1<<i)-1<=n1;x++){
				st[p][x][i]=max(st[p][x][i-1],st[p][x+(1<<i-1)][i-1]);
				if(st2[p][x][i-1]>st2[p][x+(1<<i-1)][i-1]){
					st2[p][x][i]=st2[p][x][i-1];
					sti[p][x][i]=sti[p][x][i-1];
				}
				else{
					st2[p][x][i]=st2[p][x+(1<<i-1)][i-1];
					sti[p][x][i]=sti[p][x+(1<<i-1)][i-1];
				}
			}
		}
	}
	for(int i=1;i<=n1*m;i++){
		int x=i/m;
		if(x<=0)tota[i]=get(i,1,n1);
		else{
			tota[i]=tots[x]+get(i%m,x+1,n1);
			if(i%m){
				int p=geti(i%m,1,x);
				tota[i]=max(tota[i],tots[p-1]+tots[x+1]-tots[p]+tot[u[p].x][i%m]);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=n1*m;i++){
		if(k-i<=n2*m&&k-i>=0)ans=max(ans,tota[i]+totb[k-i]);
	}
	cout<<ans;
	return 0;
}

1

qinkaiwen LV 10 @ 2026-9-22 14:31:47

首先很明显要把递减和递增的分开，一直相等的默认递减。

然后我们对两类数组分类贪心：

先令 $d1_i$ 为单调递减的数组中取 $i$ 个的最大值， $d2_i$ 为递增的。

首先对于单调递减的，我们直接将这些数组合并成一个大数组然后直接暴力贪心取最大的几个即可。

证明：

首先假设原命题不成立，那么反例就是存在一个堆，使得最优方案中它被取走的元素不连续。但这样就使得存在一个下标靠前的元素没有被取，而根据单调递减的性质那个元素被取走一定会使得答案更优。故原命题成立。

实现啥的是个人都会。

然后就是单调递增的数组。场上想的时候一开始以为和前面一样，直到对拍时才发现错了。

后面手玩了一下 hack 突然发现，对于两个没有完整取走的数组，令 $a_i$ 为第一个数组取走的最大元素， $b_j$ 为第二个数组中取走的最大元素。则一定存在 $a_i+a_{i+1}\ge a_i+b_j$ 或者 $b_j+b_{j+1} \ge a_i+b_j$ 。这个我们只需要分析一下 $a_i$ 与 $b_j$ 的大小关系就很容易证明。

这就顺便证明了：我们取递增堆的最优方案只会取走一个不完整的数组，其他都是完整的。

现在的问题就是如何实现。

我们先预先处理每一个数组的所有元素之和，然后每有 $m$ 个元素就放一个最大的进去。最后处理残堆的时候根据堆的大小选一个权值最大且没有被选入完整堆的数组（这个需要同时保证支持比大小与删除，我选择的是 set）。这便是 $d2_i$ 的初始答案。

然后就要问了，万一从完整堆里选一个出来组残堆会使答案更优呢？

那我们考虑：当前残堆大小 $len$ ，当前所有完整堆的元素之和 $\{a_i\}$ ，这些完整堆在变成残堆时的大小 $\{b_i\}$ ，当前选用的残堆大小 $c$ ，以及没有被选入完整堆的堆中元素和最大的堆的元素之和 $x$ 。

那么我们更换 $x$ 成为完整堆所能创造的最大权值为：

x-\min\{a_i-b_i\}-c

由于 $x$ 和 $c$ 在一个 $d2$ 的下标处理中是不变的，我们只需要开一个数组维护所有 $a_i-b_i$ 在每一个 $b_i$ 的最小值就行了。

剩下的就是一堆细节问题了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+10;
vector<int>a[N],s1[N];int v[N],len[N],d1[N],d2[N],s[N];
struct node{int x,id,pos;};
bool operator<(node n1,node n2){return n1.x<n2.x;}
bool operator>(node n1,node n2){return n1.x>n2.x;}
int mn[N]; 
multiset<int>se[N];
void era(int id,int x)
{
	auto it=se[id].lower_bound(x);
	se[id].erase(it);
}
int getmx(int x){return *se[x].rbegin();}
signed main()
{
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		a[i].push_back(0);s1[i].push_back(0);
		for(int j=1;j<=m;j++)
		{
			int x;cin>>x;s[i]+=x;
			if(j>1&&a[i][j-1]<x)v[i]=1;
			else if(j>1&&a[i][j-1]>x)v[i]=-1;
			a[i].push_back(x);s1[i].push_back(s[i]);
		}
		if(!v[i])v[i]=1;
	}
	for(int i=1;i<=n;i++)if(v[i]==1)
	{
		for(int j=0;j<=m;j++)
		{
			se[j].insert(s1[i][j]);
		}
	}
	priority_queue<node>q,q1;
	int siz1=0,siz2=0,sum1=0,sum2=0;
	for(int i=1;i<=n;i++)
	{
		if(v[i]==-1)
			q.push({a[i][1],i,1}),siz1+=m;
		else q1.push({s[i],i,0}),siz2+=m,sum1+=s[i];
	}
	memset(mn,0x3f,sizeof(mn));
	int len=0,sum=0;
	for(int i=1;i<siz2;i++)
	{
		len++;
		if(len==m)
		{
			node x=q1.top();q1.pop();int id=x.id;
			for(int j=0;j<=m;j++)mn[j]=min(mn[j],s[id]-s1[id][j]);
			for(int j=1;j<=m;j++)era(j,s1[id][j]);
			sum+=x.x;
			len=0;
		}
		int b=getmx(len),mx=b+sum;
		if(sum)mx=max(mx,q1.top().x-mn[len]-b+mx);
		d2[i]=mx;
	}
	d2[siz2]=sum1;
	for(int i=1;i<=siz1;i++)
	{
		node x=q.top();q.pop();
		sum2+=x.x;d1[i]=sum2;
		if(x.pos!=m)q.push({a[x.id][x.pos+1],x.id,x.pos+1});
	}
	for(int i=1;i<=k;i++)d1[i]=max(d1[i],d1[i-1]);
	for(int i=1;i<=k;i++)d2[i]=max(d2[i],d2[i-1]);
	int ans=0;
	for(int i=0;i<=k;i++)ans=max(ans,d1[i]+d2[k-i]);
	cout<<ans;
	return 0;
}

0

admin LV 10 SU @ 2026-5-3 19:22:15

传送门

题意

给定大小 $n \times m$ 的矩阵 $a_{i,j}$ ，记 $\displaystyle sum_{i, j} = \sum_{k = 1}^j a_{i, k}$ 。

可以选择 $n$ 个数 $j_1, j_2, \cdots, j_n$ 满足 $0 \le j_k \le m$ 且 $\displaystyle \sum_{k = 1}^n j_k = V$ 。求 $\displaystyle \sum_{k = 1}^n sum_{k, j_k}$ 的最大值。

$n \times m \le 3 \times 10 ^ 5$ ， $V \le n \times m$ 。

对任意 $1 \le i \le n$ 有 $a_{i, 1} \le a_{i, 2} \le \cdots \le a_{i, m}$ 或 $a_{i, 1} \ge a_{i, 2} \ge \cdots \ge a_{i, m}$ ，即对任意 $1 \le i \le n$ 有 $a_{i, j} (1 \le j \le m)$ 单调不减或单调不增。

解析

首先，我们可以将不增的和不减的分开考虑。

设 $f_x$ 为只考虑不增的时， $\displaystyle\sum_{k = 1}^n j_k = x$ 时的最大值， $g_x$ 为只考虑不减的时， $\displaystyle\sum_{k = 1}^n j_k = x$ 时的最大值。

则答案 $\displaystyle ANS = \max_{0 \le x \le V} (f_x + g_{V - x})$。

先求 $f_x$ ，其中 $0 \le x \le n \times m$ 。

设令 $a_{i, j}(1 \le j \le m)$ 不增的 $i$ 有 $I$ 个，则 $x > I \times m$ 时有 $f_x = f_{I \times m}$ 。所以只需要求 $0 \le x \le I \times m$ 时的 $f_x$ 。

贪心。将所有这样的 $i$ 对应的 $I \times m$ 个 $a_{i, j}$ 放在一起排序，取最大的 $x$ 个，它们的和就是 $f_x$ 。

:::success[证明] 只需证明这样是合法的，即证：若取了某个 $a_{i, j}$ ，则一定也取了 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, j - 1}$ 。

因为 $a_{i, 1} \ge a_{i, 2} \ge \cdots \ge a_{i, j - 1}$ ，而又是从大到小取的，所以一定也取了 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, j - 1}$ 。证毕。 :::

再求 $g_x$ ，其中 $0 \le x \le n \times m$ 。

同理，设令 $a_{i, j}(1 \le j \le m)$ 不减的 $i$ 有 $J$ 个，则 $x > J \times m$ 时有 $g_x = g_{J \times m}$ 。所以只需要求 $0 \le x \le J \times m$ 时的 $g_x$ 。

对于这样的 $i$ ，注意到 $a_{i, j} \le a_{i, j + 1}$ ，所以 $sum_{i, j - 1} + sum_{i, j + 1} \ge 2sum_{i, j}$ 。

所以 $sum_{i, j}(0 \le j \le m)$ 为下凸函数！

而 $g_x(0 \le x \le J \times m)$ 为下凸函数的卷积，所以合理猜测当 $k_i(1 \le i \le n)$ 几乎都取到边界时 $g_x$ 最大。

猜测： $g_x$ 最大时，可以使 $k_i$ 中至多有一个数 $\in (0, m)$ 。

:::success[证明] 反证法。假设有至少两个 $i$ 满足 $k_i \in (0, m)$ 。则这两行都选了但没选完。

设其中一行最后一个选的数为 $a$ ，第一个没选的数为 $b$ ，另一行最后一个选的数为 $c$ ，第一个没选的数为 $d$ 。

则 $a \le b$ ， $c \le d$ 。

若 $b \le d$ ，则 $a \le b \le d$ 。将 $a$ 去掉并加入 $d$ ，则 $g_x$ 不减，矛盾。

若 $b > d$ ，则 $c \le d < b$ 。将 $c$ 去掉并加入 $b$ ，则 $g_x$ 增加，亦矛盾。

证毕。 :::

所以 $g_x$ 取到最大值时，只有至多一行选了但没选完，其余的要么全选了要么都没选。

于是可以通过带余除法确定选了但没选完的那一行选了几个，以及有多少行全选了。

设 $x = qm+r$ ，其中 $q$ 为非负整数， $r \in [0, m)$ 。

分以下两种情况：

若 $r = 0$ ，则一定是有 $q$ 行全选了，其余的都没选。于是取总和最大的 $q$ 行即可。
若 $r > 0$ ，则有 $q$ 行全选了，有一行只选了 $r$ 个，其余的行没选。

首先贪心的选取总和最大的 $q$ 行为全选的，则取剩下的行中 $sum_{i, r}$ 最大的 $i$ 对应的行选 $r$ 个。

可以发现这样贪心是不对的，于是再考虑选 $r$ 个的行在总和最大的 $q$ 行中的情况。此时需要选剩下的当中总和最大的 $q$ 行全选，即总和最大的 $q + 1$ 行除去选 $r$ 个的行。

所以可以先选了总和最大的 $q + 1$ 行，再选其中的一行删掉后 $m - r$ 个。取其中后 $m - r$ 个的和最小的一行即可。

其中需要求总和最大的 $q$ 行的和，不在总和最大的 $q$ 行中的行的 $sum_{i, r}$ 的最大值，总和最大的 $q + 1$ 行中后 $m - r$ 个的和的最小值，如果先按照总和从大到小的顺序将这 $n$ 行排序，则依次为前缀和，后缀最大值，前缀最小值，可以预处理。

这样就可以求出 $g_x$ 了。最后再求 $ANS$ 即可。

时间复杂度 $O(nm\log nm)$ 。

:::success[代码]

#define N 300005
#define ll long long
int n, m, k; ll a[N];
struct node {
    vector<ll> sum;
    node () {}
    void init() {sum.resize(m + 1, 0);}
    friend bool operator < (node a, node b) {return a.sum[m] > b.sum[m];}
};
node nd[N];
ll sum[N];
ll pre[N], suc[N];
int f(int i, int j) {return (i - 1) * m + j;}
int cnt = 0;
priority_queue<ll> q;
ll ans[N], ans_[N];
int main() {
    n = read<int>(); m = read<int>(); k = read<int>();
    for (int i = 1; i <= n; i++) {
        bool flg = true;
        for (int j = 1; j <= m; j++) {
            a[j] = read<ll>();
            if (j > 1 && a[j] > a[j - 1]) flg = false;
        } if (flg) {
            for (int j = 1; j <= m; j++) q.push(a[j]);
        } else {
            nd[++cnt].init();
            for (int j = 1; j <= m; j++) nd[cnt].sum[j] = nd[cnt].sum[j - 1] + a[j];
        }
    } sort(nd + 1, nd + cnt + 1); ll sm = 0;
    for (int i = 1; i <= (n - cnt) * m; i++) {
        sm += q.top(); q.pop();
        ans[i] = sm;
    } for (int i = (n - cnt) * m + 1; i <= n * m; i++) ans[i] = ans[i - 1];
    for (int i = 1; i <= cnt; i++) sum[i] = sum[i - 1] + nd[i].sum[m];
    for (int i = 1; i <= cnt; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1) pre[f(i, j)] = nd[i].sum[j] - nd[i].sum[m];
            else pre[f(i, j)] = max_(pre[f(i - 1, j)], nd[i].sum[j] - nd[i].sum[m]);
        }
    } for (int i = cnt; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            if (i == cnt) suc[f(i, j)] = nd[i].sum[j];
            else suc[f(i, j)] = max_(suc[f(i + 1, j)], nd[i].sum[j]);
        }
    } for (int i = 1; i <= cnt * m; i++) {
        if (i % m == 0) {
            ans_[i] = sum[i / m];
        } else {
            int x = i / m, r = i % m;
            ans_[i] = max_(sum[x] + suc[f(x + 1, r)], sum[x + 1] + pre[f(x + 1, r)]);
        }
    } for (int i = cnt * m + 1; i <= n * m; i++) ans_[i] = ans_[i - 1];
    ll ANS = 0;
    for (int i = 0; i <= k; i++) ANS = max_(ANS, ans[i] + ans_[k - i]);
    writeln(ANS); return fl();
}

:::

提交记录

5 条题解

题意

解析

THE END

信息

状态

开发

支持

关于

5 条题解

题意

解析

THE END

[PA 2026] 堆煎饼 / Stosy naleśników

信息

状态

开发

支持

关于

还没有账户？

登录