oj.uz

Submission #64316

# Submission time Handle Problem Language Result Execution time Memory
64316 2018-08-04T05:03:21 Z antimirage Homecoming (BOI18_homecoming) C++17
13 / 100
 286 ms 79004 KB 
/**
    Death gotta be easy cause life is hard
**/
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>
#include "homecoming.h"

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e6 + 5;

int n, k, a[N], b[N];

long long dp[N][2], pref[N], inf = 1e18, ans;

long long sum(int i)
{
    return pref[i + k - 1] - (i == 0 ? 0 : pref[i - 1]);
}
long long Main( bool fl )
{
    ans = 0;
    for (int i = 0; i < n + n; i++)
        pref[i] = pref[i - 1] + b[i];

    for (int i = 0; i < n; i++)
        dp[i][0] = dp[i][1] = -inf;

    if (fl)
        dp[0][1] = a[0] + sum(0);
    else
        dp[0][0] = 0;

    for (int i = 1; i < n; i++)
    {
        dp[i][0] = dp[i - 1][0];

        if (i >= k)
            dp[i][0] = max(dp[i][0], dp[i - k][1]);

        if (i + k - 1 < n)
            dp[i][1] = max( dp[i - 1][1] + b[i + k - 1], dp[i - 1][0] + sum(i) ) + a[i];
        else
        {
            if (fl)
                dp[i][1] = max( dp[i - 1][1], dp[i - 1][0] + pref[n - 1] - pref[i - 1] ) + a[i];
            else
                dp[i][1] = max( dp[i - 1][1] + b[i + k - 1], dp[i - 1][0] + sum(i) ) + a[i];
        }
        ans = max(ans, dp[i][0]);
        ans = max(ans, dp[i][1]);
    }
    return ans;
}

long long solve(int N, int K, int A[], int B[])
{
    n = N, k = K;
    for (int i = 0; i < n; i++)
        a[i] = A[i], b[i] = -B[i];

    for (int i = 0; i < n; i++)
        b[i + n] = -B[i];

    return max(Main(0), Main(1) );
}

/**
1
3 2
40 80 100
140 0 20
**/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Incorrect 4 ms 768 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 26016 KB Output is correct
2 Correct 8 ms 26016 KB Output is correct
3 Incorrect 286 ms 79004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 4 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Incorrect 4 ms 768 KB Output isn't correct