oj.uz

Submission #60654

# Submission time Handle Problem Language Result Execution time Memory
60654 2018-07-24T13:17:40 Z SpaimaCarpatilor Homecoming (BOI18_homecoming) C++17
31 / 100
 1000 ms 28028 KB 
#include "homecoming.h"
#include<bits/stdc++.h>

using namespace std;

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

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

long long solve (int N, int K, int *aa, int *bb)
{
    A = new int[2 * N], B = new int[2 * N];
    sB = new long long[2 * N];
    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];
    for (int i=0; i<N; i++)
    {
        ///assume this one is free
        x[i] = -INF, y[i] = 0;
        int lst = i + N - K;
        for (int j=i + 1; j<=lst; j++)
        {
            x[j] = max (x[j - 1] + A[j] - B[j + K - 1], y[j - 1] + A[j] - getSB (j, j + K - 1));
            y[j] = max (x[j - 1], y[j - 1]);
        }
        long long curr = max (x[lst], y[lst]);
        if (curr > ans)
            ans = curr;
    }
    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 564 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 5 ms 576 KB Output is correct
5 Correct 2 ms 576 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 3 ms 564 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 5 ms 576 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 44 ms 840 KB Output is correct
8 Correct 20 ms 840 KB Output is correct
9 Correct 129 ms 844 KB Output is correct
10 Correct 4 ms 844 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 28028 KB Time limit exceeded
2 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 3 ms 564 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 5 ms 576 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 44 ms 840 KB Output is correct
8 Correct 20 ms 840 KB Output is correct
9 Correct 129 ms 844 KB Output is correct
10 Correct 4 ms 844 KB Output is correct
11 Execution timed out 1077 ms 28028 KB Time limit exceeded
12 Halted 0 ms 0 KB -