제출 #126030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126030		TadijaSebez	Cake 3 (JOI19_cake3)	C++11	24 / 100	4021 ms	75944 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll inf=1e18;
const int N=200050;
const int M=18*N;
int v[N],c[N],id[N],idv[N],pos[N],n,m;
int ls[M],rs[M],tsz,root[N],sz[M];
ll sum[M];
void Set(int p, int &c, int ss, int se, int qi, ll x)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+x;sz[c]=sz[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,x);
	else Set(rs[p],rs[c],mid+1,se,qi,x);
}
ll Get(int p, int c, int ss, int se, int k)
{
	if(ss==se) return k>0?sum[c]:0;
	int mid=ss+se>>1;
	int A=sz[ls[c]]-sz[ls[p]];
	ll B=sum[ls[c]]-sum[ls[p]];
	if(A<=k) return B+Get(rs[p],rs[c],mid+1,se,k-A);
	else return Get(ls[p],ls[c],ss,mid,k);
}
map<pair<int,int>,ll> dp;
ll Get(int l, int r)
{
	if(dp.count({l,r})) return dp[{l,r}];
	return dp[{l,r}]=v[id[l]]+c[id[l]]+v[id[r]]-c[id[r]]+Get(root[l],root[r-1],1,n,m-2);
}
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
	sort(id+1,id+1+n,[&](int i, int j){ return c[i]<c[j];});
	sort(idv+1,idv+1+n,[&](int i, int j){ return v[i]>v[j];});
	for(int i=1;i<=n;i++) pos[idv[i]]=i;
	for(int i=1;i<=n;i++) Set(root[i-1],root[i],1,n,pos[id[i]],v[id[i]]);
	vector<int> L,R;
	for(int i=1;i<=n;i++) if(i==1 || v[id[i]]+c[id[i]]>v[L.back()]+c[L.back()]) L.pb(i);
	for(int i=n;i>=1;i--) if(i==n || v[id[i]]-c[id[i]]>v[R.back()]-c[R.back()]) R.pb(i);
	reverse(R.begin(),R.end());
	ll ans=-inf;
	for(int i=0,j=0;i<R.size();i++)
	{
		while(j+1<L.size() && R[i]-L[j+1]+1>=m && Get(L[j],R[i])<=Get(L[j+1],R[i])) j++;
		if(R[i]-L[j]+1>=m) ans=max(ans,Get(L[j],R[i]));
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i-j+1>=m) ans=max(ans,Get(j,i));
	printf("%lld\n",ans);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'void Set(int, int&, int, int, int, long long int)':
cake3.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'long long int Get(int, int, int, int, int)':
cake3.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<R.size();i++)
                  ~^~~~~~~~~
cake3.cpp:49:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j+1<L.size() && R[i]-L[j+1]+1>=m && Get(L[j],R[i])<=Get(L[j+1],R[i])) j++;
         ~~~^~~~~~~~~
cake3.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:37:58: 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("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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