이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 0;
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;
~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |