Submission #3776619

---

Source Code Expand

#pragma GCC target("sse4")
#pragma GCC optimize("O3")

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

using ll = long long;

const int N = 1e5 + 5, W = 1e6 + 5;
const ll inf = 1e18;

int n, m;
int taste[205][5005];
ll dist[5005];
ll dp[205][5005];
ll acc[5005];
ll get(int l, int r){
	if(l >= r)return 0;
	return acc[r-1] - acc[l-1];
}
void calc(int ticket, int s, int e, int optL, int optR){
	if(s > e)return;
	int md = (s+e)>>1;
	int optI = optL;
	dp[ticket][md] = -inf;
	for(int i = optL; i <= optR; i++){
		if(dp[ticket-1][i] - get(i,md) + taste[ticket][i] > dp[ticket][md]){
			dp[ticket][md] = dp[ticket-1][i] - get(i,md) + taste[ticket][i];
			optI = i;
		}
	}
	calc(ticket,s,md-1,optL,optI);
	calc(ticket,md+1,e,optI,optR);
}
int main() {

	cin >> n >> m;

	for(int i = 1; i < n; i++){
		cin >> dist[i];
		acc[i] = acc[i-1] + dist[i];
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> taste[j][i];
		}
	}

	for(int i = 1; i <= m; i++)
		calc(i,1,n,1,n);

	cout << *max_element(dp[m] + 1, dp[m] + n + 1);

	return 0;
}

Submission Info

Judge Result