oj.uz

답안 #60700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60700 2018-07-24T14:34:57 Z SpaimaCarpatilor Homecoming (BOI18_homecoming) C++17
0 / 100
 291 ms 110128 KB 
#include "homecoming.h"
#include<bits/stdc++.h>

using namespace std;

const long long INF = 1LL << 60;
int K, *A, *B;
long long *sB, x[2000009], y[2000009];

long long getSB (int i, int j)
{
    if (i > j) return 0;
    if (i == 0) return sB[j];
    return sB[j] - sB[i - 1];
}

long long solve (int N, int kk, int *aa, int *bb)
{
    A = new int[2 * N], B = new int[2 * N];
    sB = new long long[2 * N], K = kk;
    for (int i=0; i<N; i++)
        A[i] = A[N + i] = aa[i], B[i] = B[N + i] = bb[i];
    sB[0] = B[0];
    for (int i=1; i<2 * N; i++)
        sB[i] = sB[i - 1] + B[i];
    long long ans = 0;
    for (int i=0; i<N; i++)
        ans += A[i] - B[i];
    ans = max (ans, 0LL);
    if (N == K)
        return ans;
    x[0] = -INF, y[0] = 0;
    for (int i=1; i<N; i++)
    {
        x[i] = max (x[i - 1] + A[i] - B[i + K - 1], y[i - 1] + A[i] - getSB (i, i + K - 1));
        y[i] = max (x[i - 1], y[i - 1]);
    }
    ans = max (ans, max (x[N - 1], y[N - 1]));
    x[0] = A[0] - getSB (0, K - 1);
    y[0] = -INF;
    for (int i=1; i<N; i++)
    {
        long long c0 = (i + K - 1 >= N ? 0 : B[i + K - 1]);
        int l = i, r = min (i + K - 1, N - 1);
        long long c1 = getSB (l, r);
        x[i] = max (x[i - 1] + A[i] - c0, y[i - 1] + A[i] - c1);
        y[i] = max (x[i - 1], y[i - 1]);
    }
    return ans;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 27956 KB Output is correct
2 Correct 7 ms 27956 KB Output is correct
3 Correct 291 ms 110128 KB Output is correct
4 Correct 4 ms 110128 KB Output is correct
5 Incorrect 19 ms 110128 KB Output isn't correct

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Incorrect 3 ms 484 KB Output isn't correct
4 Halted 0 ms 0 KB -