1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<vector<long long int>>v(n,vector<long long int>(m));
	vector<vector<long long int>>ros,mal;
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<m; j++)
			cin>>v[i][j];
		bool ni=0;
		for(int j=1; j<m; j++)
			if(v[i][j-1]<v[i][j])
			{
				ni=1;
				break;
			}
		if(ni)
			ros.push_back(v[i]);
		else
			mal.push_back(v[i]);
	}
	vector<long long int>resm(k+1);
	priority_queue<pair<long long int,pair<int,int>>>q;
	for(int i=0; i<(int)mal.size(); i++)
		q.push({mal[i][0],{i,0}});
	for(int i=1; i<=k; i++)
	{
		if(q.empty())
			break;
		auto p=q.top();
		q.pop();
		resm[i]=resm[i-1]+p.first;
		if(p.second.second+1<m)
			q.push({mal[p.second.first][p.second.second+1],{p.second.first,p.second.second+1}});
	}
	/*for(int i=0; i<resm.size(); i++)
	{
		cout<<"resm["<<i<<"]="<<resm[i]<<"\n";
	}*/
	long long int res=0;
	vector<pair<long long int,int>>sm;
	vector<vector<long long int>>smp(ros.size(),vector<long long int>(m));
	vector<priority_queue<pair<long long int,int>>>suf(m+1);
	vector<priority_queue<long long int>>pref(m+1);
	for(int i=0; i<ros.size(); i++)
	{
		smp[i][0]=ros[i][0];
		suf[1].push({smp[i][0],i});
		for(int j=1; j<m; j++)
		{
			smp[i][j]=smp[i][j-1]+ros[i][j];
			suf[j+1].push({smp[i][j],i});
		}
		sm.push_back({smp[i][m-1],i});
	}
	sort(sm.begin(),sm.end());
	reverse(sm.begin(),sm.end());
	vector<bool>used(ros.size(),0);
	int ile=0;
	long long int sump=0;
	for(int i=0; i<=k; i++)
	{
		if(i>(int)ros.size()*m)
			break;
		long long int pot=sump;
		if(i%m!=0)
		{//dorzucamy sufiks
			auto pom=suf[i%m].top();
			while(used[pom.second])
			{
				suf[i%m].pop();
				pom=suf[i%m].top();
			}
			pot+=pom.first;
			if(ile)
			{
				auto pom1=pref[i%m].top();
				pot=max(pot,sump+sm[ile].first+pom1);
			}
		}
		res=max(res,pot+resm[k-i]);
		if(ros.size()>0&&(i+1)%m==0)
		{
			sump+=sm[ile].first;
			used[sm[ile].second]=1;
			for(int i=0; i<m; i++)
				pref[i+1].push(smp[sm[ile].second][i]-sm[ile].first);
			ile++;
		}
	}
	cout<<res<<"\n";
}