oj.uz

Submission #60663

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

using namespace std;

const long long INF = 1LL << 60;
int K, *A, *B;
long long *sB;

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

void combine (long long ans[2][2], long long dp1[2][2], long long dp2[2][2])
{
    for (int i=0; i<2; i++)
        for (int j=0; j<2; j++)
            ans[i][j] = max (dp1[i][0] + dp2[0][j], dp1[i][1] + dp2[1][j]);
}

long long dp[8000009][2][2];
void build (int nod, int st, int dr)
{
    if (st == dr)
    {
        dp[nod][1][0] = dp[nod][0][0] = 0;
        dp[nod][1][1] = A[st] - B[st + K - 1];
        dp[nod][0][1] = A[st] - getSB (st, st + K - 1);
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
    combine (dp[nod], dp[f1], dp[f2]);
}

long long ansQ[2][2];
void getQuery (int nod, int st, int dr, int x, int y)
{
    if (x <= st && dr <= y)
    {
        if (x == st) memcpy (ansQ, dp[nod], sizeof (dp[nod]));
        else
        {
            long long aux[2][2];
            memcpy (aux, ansQ, sizeof (ansQ));
            combine (ansQ, aux, dp[nod]);
        }
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    if (x <= mij) getQuery (f1, st, mij, x, y);
    if (mij < y) getQuery (f2, mij + 1, dr, x, y);
}

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;
    build (1, 1, N - 1 + N - K);
    for (int i=0; i<N; i++)
    {
        ///assume this one is free
        getQuery (1, 1, N - 1 + N - K, i + 1, i + N - K);
        long long curr = max (ansQ[0][0], ansQ[0][1]);
        if (curr > ans)
            ans = curr;
    }
    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 5 ms 1272 KB Output is correct
8 Correct 5 ms 1272 KB Output is correct
9 Correct 6 ms 1744 KB Output is correct
10 Correct 4 ms 1744 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 85964 KB Output is correct
2 Correct 19 ms 85964 KB Output is correct
3 Execution timed out 1044 ms 263168 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 3 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 628 KB Output is correct
7 Correct 5 ms 1272 KB Output is correct
8 Correct 5 ms 1272 KB Output is correct
9 Correct 6 ms 1744 KB Output is correct
10 Correct 4 ms 1744 KB Output is correct
11 Correct 454 ms 85964 KB Output is correct
12 Correct 19 ms 85964 KB Output is correct
13 Execution timed out 1044 ms 263168 KB Time limit exceeded
14 Halted 0 ms 0 KB -