# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
137861 | zoooma13 | Cake 3 (JOI19_cake3) | C++14 | 33 ms | 31736 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 2003
#define INF 0x3f3f3f3f3f3f3f3f
int n ,m;
int c[MAX_N] ,v[MAX_N];
long long dp[MAX_N][MAX_N];
long long solve(int p ,int l){
if(p == n)
return -INF;
auto&ret = dp[p][l];
if(~ret)
return ret;
if(l == 1)
return ret = max(-2LL*c[p]+v[p] ,solve(p+1 ,l));
return ret = max(v[p]+solve(p+1 ,l-1) ,solve(p+1 ,l));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0; i<n; i++)
scanf("%d%d",&v[i],&c[i]);
vector <int> ord(n);
iota(ord.begin() ,ord.end() ,0);
sort(ord.begin() ,ord.end() ,[](int&i ,int&j){
return c[i] < c[j];
});
vector <int> V(n) ,C(n);
for(int i=0; i<n; i++)
V[i] = v[ord[i]] ,C[i] = c[ord[i]];
for(int i=0; i<n; i++)
v[i] = V[i] ,c[i] = C[i];
memset(dp ,-1 ,sizeof dp);
long long ans = 0LL;
for(int i=0; i<=n-m; i++)
ans = max(ans ,solve(i+1 ,m-1)+v[i]+2*c[i]);
printf("%lld\n",ans);
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |