이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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; i++) ans=max(ans, dp[i]);
printf("%lld", ans);
return 0;
}
컴파일 시 표준 에러 (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);
~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |