oj.uz

Submission #59729

# Submission time Handle Problem Language Result Execution time Memory
59729 2018-07-23T00:57:00 Z model_code Homecoming (BOI18_homecoming) C++17
31 / 100
 195 ms 32036 KB 
// Andrei-Costin Constantinescu
// O(N) - Dynamic Programming
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const int NMAX = 2000000;

int N, K;
int A[2 * NMAX + 5]; // Subjects
int B[2 * NMAX + 5]; // Textbooks

typedef long long int lint;
const lint INF = 2E16L;

lint sPartB[2 * NMAX + 5];
inline lint getSPartB(int l, int r) {
    assert(1 <= l && 1 <= r && l <= 2 * N && r <= 2 * N && l <= r);
    return sPartB[r] - sPartB[l - 1];
}

lint taken[NMAX], notTaken[NMAX];
inline void updateDp(lint &where, const lint val) {
    if (val > where)
        where = val;
}

lint computeDp(bool forceFirst) {
    for (int i = 0; i <= N; ++ i)
        taken[i] = notTaken[i] = -INF;

    if (forceFirst)
        taken[1] = A[1] - getSPartB(1, K);
    else
        notTaken[1] = 0;

    lint ans = -INF;
    for (int i = 1; i <= N; ++ i) {
        // notTaken[i] -> taken[i], decrease less if ForceFirst
        if (!forceFirst)
            updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, i + K - 1));
        else
            updateDp(taken[i], notTaken[i] + A[i] - getSPartB(i, min(N, i + K - 1)));

        updateDp(ans, taken[i]), updateDp(ans, notTaken[i]);

        // taken[i] - B[i + K] + A[i + K] -> taken[i + 1]
        if (i + 1 <= N) {
            if (!forceFirst || i + K <= N)
                updateDp(taken[i + 1], taken[i] - B[i + K] + A[i + 1]);
            else
                updateDp(taken[i + 1], taken[i] + A[i + 1]);
        }

        // taken[i] -> notTaken[i + K];
        if (i + K <= N)
            updateDp(notTaken[i + K], taken[i]);

        // notTaken[i] -> notTaken[i + 1]
        if (i + 1 <= N)
            updateDp(notTaken[i + 1], notTaken[i]);

    }
    if (ans < 0)
        return 0;
    else
        return ans;
}

lint solve(int n, int k, int a[], int b[]) {
    N = n, K = k;
    assert(1 <= N && 1 <= K && N < NMAX && K <= N);

    for (int i = 1; i <= N; ++ i) {
        A[i] = a[i - 1];
        A[N + i] = A[i];
    }
    for (int i = 1; i <= N; ++ i) {
        B[i] = b[i - 1];
        B[N + i] = B[i];
    }
    for (int i = 1; i <= 2 * N; ++ i)
        sPartB[i] = sPartB[i - 1] + B[i];
    return max(computeDp(false), computeDp(true));
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 540 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 540 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 856 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 4 ms 856 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 3 ms 856 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 27940 KB Output is correct
2 Correct 6 ms 27940 KB Output is correct
3 Runtime error 195 ms 32036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 540 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 3 ms 592 KB Output is correct
6 Correct 3 ms 856 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 4 ms 856 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 3 ms 856 KB Output is correct
11 Correct 79 ms 27940 KB Output is correct
12 Correct 6 ms 27940 KB Output is correct
13 Runtime error 195 ms 32036 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -