记录详情

#include <bits/stdc++.h>
using namespace std;
long long n,a[1005][1005]={},ans_consumption=1e9,ans_sum=-1e9,max_delegation[1005],k=0;
void find_max_delegation() {
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=i;j++)
			max_delegation[i]=max(max_delegation[i],a[i][j]);
}
void oventurn_right() {
	long long b[1005][1005]={};
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=i;j++)
			b[i][j]=a[n-j+1][i-j+1];
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=i;j++)
			a[i][j]=b[i][j];
}
void dynamic_planning(){
	long long dp[1005][1005]={},consumption[1005][1005];
	for (long long i=n;i>=1;i--) {
		for (long long j=1;j<=i;j++) {
			if (consumption[i+1][j]+1>=consumption[i+1][j+1]+1) {
				dp[i][j]=dp[i+1][j+1]+max_delegation[i];
				consumption[i][j]=consumption[i+1][j+1];
				if(max_delegation[i]!=a[i][j])
					consumption[i][j]+=1;
			} else {
				dp[i][j]=dp[i+1][j]+max_delegation[i];
				consumption[i][j]=consumption[i+1][j];
				if(max_delegation[i]!=a[i][j])
					consumption[i][j]+=1;
			}
		}
	}
	if (ans_sum<dp[1][1]) {
		ans_sum=dp[1][1];
		ans_consumption=consumption[1][1]+k;
	} else if (ans_sum==dp[1][1]) {
		ans_sum=dp[1][1];
		ans_consumption=min(ans_consumption,consumption[1][1]+k);
	}
}
int main() {
	cin >>n;
	for (long long i=1;i<=n;i++)
		for (long long j=1;j<=i;j++)
			cin >>a[i][j];
	memset(max_delegation,0,sizeof(max_delegation));
	find_max_delegation();
	dynamic_planning();
	memset(max_delegation,0,sizeof(max_delegation));
	k=5;
	oventurn_right();
	find_max_delegation();
	dynamic_planning();
	memset(max_delegation,0,sizeof(max_delegation));
	k=10;
	oventurn_right();
	find_max_delegation();
	dynamic_planning();
	cout << ans_sum << ' '<<ans_consumption << endl;
    return 0;
}