Submission #120797

#	Time	Username	Problem	Language	Result	Execution time	Memory
120797		imyujin	Cake 3 (JOI19_cake3)	C++14	100 / 100	1104 ms	188720 KiB

cake3

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 200005

typedef long long lint;
typedef pair<lint, lint> pll;
typedef pair<lint, int> pli;

struct NOD{
	NOD *lef, *rig;
	int cnt;
	lint sum;

	NOD();
} *nil, *pst[MAXN];

NOD::NOD(){
	lef=rig=nil;
	cnt=0;
	sum=0ll;
}

const lint LINF=1ll<<50;
int N, M;
pll CV[MAXN];
pli vs[MAXN];
int vidx[MAXN];
lint dp[MAXN];

void mkpst(NOD *bf, NOD *nw, int l, int r, int x){
	//printf("mkpst(%d %d %d %lld)\n", l, r, x, vs[x].first);
	//printf("%d", bf==nil?1:0);
	//printf("%d", bf->cnt);
	nw->cnt=bf->cnt+1;
	nw->sum=bf->sum+vs[x].first;
	if(l==r) return;
	int m=(l+r)/2;
	if(x<=m){
		nw->lef=new NOD();
		nw->rig=bf->rig;
		mkpst(bf->lef, nw->lef, l, m, x);
	}
	else{
		nw->lef=bf->lef;
		nw->rig=new NOD();
		mkpst(bf->rig, nw->rig, m+1, r, x);
	}
}

lint gpst(NOD *pa, NOD *pb, int l, int r, int k){
	//printf("gpst(l=%d, r=%d, k=%d)\n", l, r, k);
	if(k==0) return 0ll;
	if(k >= pb->cnt - pa->cnt) return pb->sum - pa->sum;
	int m=(l+r)/2;
	int cr=pb->rig->cnt - pa->rig->cnt;
	if(cr>=k) return gpst(pa->rig, pb->rig, m+1, r, k);
	else return pb->rig->sum - pa->rig->sum + gpst(pa->lef, pb->lef, l, m, k-cr);
}

void dnc(int al, int ar, int bl, int br){
	//printf("dnc(al=%d, ar=%d, bl=%d, br=%d)\n", al, ar, bl, br);
	if(ar<al) return;
	int am=(al+ar)/2, bm;
	lint sum;
	dp[am]=-LINF;
	for(int i=max(bl, am+M-1); i<=br; i++){
		int s=1, e=N;
		lint ndp=gpst(pst[am], pst[i-1], 1, N, M-2)+2*CV[am].first-2*CV[i].first+CV[am].second+CV[i].second;
		//printf("ndp(i=%d)=%lld\n", i, ndp);
		if(ndp>dp[am]){
			dp[am]=ndp;
			bm=i;
		}
	}
	//printf("dp[%d]=%lld, bm=%d\n", am, dp[am], bm);
	if(al<ar){
		dnc(al, am-1, bl, bm);
		dnc(am+1, ar, bm, br);
	}
}

int main(){
	lint ans=-LINF;

	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf("%lld%lld", &CV[i].second, &CV[i].first);

	sort(CV+1, CV+N+1);
	for(int i=1; i<=N; i++) vs[i]=make_pair(CV[i].second, i);
	sort(vs+1, vs+N+1);
	for(int i=1; i<=N; i++) vidx[vs[i].second]=i;

	//for(int i=1; i<=N; i++) printf("%d ", vidx[i]);
	//printf("\n");

	nil=new NOD();
	nil->lef=nil->rig=nil;

	pst[0]=nil;
	//printf("%d", nil->cnt);
	for(int i=1; i<=N; i++){
		pst[i]=new NOD();
		mkpst(pst[i-1], pst[i], 1, N, vidx[i]);
	}

	dnc(1, N-M+1, M, N);
	for(int i=1; i<=N-M+1; i++) ans=max(ans, dp[i]);

	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:70:7: warning: unused variable 's' [-Wunused-variable]
   int s=1, e=N;
       ^
cake3.cpp:70:12: warning: unused variable 'e' [-Wunused-variable]
   int s=1, e=N;
            ^
cake3.cpp:67:7: warning: unused variable 'sum' [-Wunused-variable]
  lint sum;
       ^~~
cake3.cpp: In function 'int main()':
cake3.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
cake3.cpp:89:31: 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%lld", &CV[i].second, &CV[i].first);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp: In function 'void dnc(int, int, int, int)':
cake3.cpp:80:6: warning: 'bm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   dnc(al, am-1, bl, bm);
   ~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76