제출 #138040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138040		rajarshi_basu	Cake 3 (JOI19_cake3)	C++14	24 / 100	4030 ms	10456 KiB

cake3

#include <bits/stdc++.h>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define pb push_back
#define vi vector<int>
#define ff first
#define ss second
#define vv vector
#define ii pair<int,int>

using namespace std;

const int MAXN = 2e5 + 1;
const ll INF = 1e17;

int n,m;

ll color[MAXN];
ll v[MAXN];

ll dp[MAXN];
int lptr;
int rptr;

ll cost(int l,int r){
	vv<ll> a;
	FORE(i,l,r)a.pb(v[i]);
	sort(a.begin(),a.end());reverse(a.begin(),a.end());
	if(a.size() < m)return -INF;
	ll sum = 0;
	FOR(i,m)sum += a[i];
	return sum;
}

void recurse(int l,int r,int x,int y){
	int mid = (l+r)/2;
	ll mx = -INF;
	int optj = x;
	FORE(i,x,min(mid,y)){
		ll cst = cost(i,mid) - 2*(color[mid] - color[i]);
		if(cst > mx){
			optj = i;
			mx = cst;
		}
	}
	dp[mid] = mx;
	if(l == r)return;
	recurse(l,mid,x,optj);
	recurse(mid+1,r,optj,y);
}

int main(){
	cin >> n >> m;
	vv<ii> all;
	FOR(i,n){
		int a,b;
		cin >> a >> b;
		all.pb({b,a});
	}
	sort(all.begin(),all.end());
	FOR(i,n)color[i] = all[i].ff,v[i] = all[i].ss;
	recurse(0,n-1,0,n-1);
	ll mx = -INF;
	FOR(i,n){
		mx = max(mx,dp[i]);
	}
	cout << mx << endl;
	return 0;
}

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

cake3.cpp: In function 'long long int cost(int, int)':
cake3.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a.size() < m)return -INF;
     ~~~~~~~~~^~~

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