Submission #1513533

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,m;
ll c[5005],e[5005][205];
ll ans;
struct segtree{
	int seg[(1<<14)];
	void init(int a,int x){
		a += (1<<13)-1; seg[a] = x;
		while(a){
			a=(a-1)/2;
			seg[a] = max(seg[a*2+1],seg[a*2+2]);
		}
	}
	int query(int a,int b,int k,int l,int r){
		if(r<a||b<l) return 0;
		if(a<=l&&r<=b) return seg[k];
		return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2+1,r));
	}
}S[205];
pair<ll,int> score(int L,int R,int RR){
	ll y[205];
	pair<ll,int> X = mp(-1e18,0);
	ll sum = 0;
	for(int i=1;i<=m;i++){
		y[i] = S[i].query(L,R,0,0,(1<<13)-1);
		sum += y[i];
	}
	X = max(X,mp(sum+c[L-1]-c[R-1],R));
	for(int i=R+1;i<=RR;i++){
		for(int j=1;j<=m;j++){
			if(y[j] < e[i][j]){
				sum += e[i][j]-y[j];
				y[j] = e[i][j];
			}
		}
		X = max(X,mp(sum+c[L-1]-c[i-1],i));
	}
	return X;
}
void go(int L,int R,int a,int b){
	if(L>R || a>b) return;
	int mid = (L+R)/2;
	int p[205]={};
	pair<ll,int> X = mp(-1e18,0);
	for(int x=a;x<=b;x++){
		if(x>=mid){
			X = max(X,score(mid,x,b));
			break;
		}
	}
	ans = max(ans,X.fi);
	go(L,mid-1,a,X.sc);
	go(mid+1,R,X.sc,b);
}
int main(){
	cin >> n >> m;
	for(int i=1;i<n;i++) scanf("%lld",&c[i]);
	for(int i=2;i<n;i++) c[i] += c[i-1];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		scanf("%lld",&e[i][j]); S[j].init(i,e[i][j]);
	}
	
	go(1,n,1,n);
	cout << ans << endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%lld",&c[i]);
                                          ^
./Main.cpp:77:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&e[i][j]); S[j].init(i,e[i][j]);
                         ^

Judge Result