Wannafly 챌 린 지 12 B - T95 다이어트 dp

1897 단어 dp
링크: 클릭 하여 링크 열기
우 객 망
시간 제한: C / C + + 1 초, 기타 언어 2 초
공간 제한: C / C + + 262144 K, 기타 언어 524288 K
64bit IO Format: %lld
제목 설명
T95 가 속 도 를 올 렸 지만 그녀 는 자신 이 너무 느리다 고 느 꼈 다!
그래서 T95 는 다이 어 트 를 결정 했다. 그러나 T95 는 맥 도 날 드 를 좋아한다.
현재 n 가지 코스 가 있 는데 n 개의 맥 도 날 드, i 조 코스 의 고통 치 는 ai 이 고 i 번 째 맥 도 날 드 의 즐거움 치 는 bi 이다.
살 을 빼 기 위해 T95 가 먹 는 맥 도 날 드 횟수 는 그녀 가 뛰 는 횟수 보다 많 을 수 없다.
T95 가 너무 무 거 워 서 코스 마다 한 번 달리 면 고장 이 난다.
T95 는 서로 다른 맛 을 좋아 하기 때문에 맥 도 날 드 는 한 번 씩 가장 많이 먹는다.
민 스 크 항공우주 국 의 꿀 버그 로 인해 T95 는 세 번 뛸 때마다 추가 로 m 개의 음악 값 을 받는다.
지금 T95 는 그녀 가 얻 을 수 있 는 가장 큰 (즐거움 의 값 과 - 고통 의 값 의 합) 이 얼마 인지 알 고 싶 어 합 니 다.
입력 설명:
 
   

第一行两个数n,m

第二行n个数表示ai

第三行n个数表示bi

输出描述:

           

a 작은 것 부터 큰 것 까지, b 큰 것 부터 작은 것 까지 각각 정렬, c [i] = b [i] - a [i]
상태 이동 공식 dp [i] = dp [i - 1] + c [i] + (i + 1)% 3 = = 0?m : 0;
#include
using namespace std;
typedef long long ll;
typedef pairP;
const int inf = 0x3f3f3f3f;
const int N = 1000000 + 5;
const int mod = 1e9 + 7;
ll a[N], b[N], c[N], dp[N];
bool cmp(const int&a, const int&b)
{
    return a > b;
}
int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    for(int i = 0; i < n; i++) scanf("%lld", &b[i]);
    sort(a, a + n); sort(b, b + n, cmp);
    ll ans = 0LL;
    for(int i = 0; i < n; i++)
    {
        c[i] = b[i] - a[i];
    }
    dp[0] = c[0];
    ll maxi = dp[0];
    for(int i = 1; i < n; i++)
    {
        dp[i] = c[i];
        if((i+1)%3 == 0)
            dp[i] += m;
        dp[i] += dp[i-1];
        maxi = max(maxi, dp[i]);
    }
    printf("%lld
", maxi); }

좋은 웹페이지 즐겨찾기