oj.uz

Submission #64333

# Submission time Handle Problem Language Result Execution time Memory
64333 2018-08-04T05:40:44 Z antimirage Homecoming (BOI18_homecoming) C++17
100 / 100
 304 ms 135068 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 = 4e6 + 5;

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

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

long long sum(int i)
{
    return pref[i + k - 1] - (i == 0 ? 0 : pref[i - 1]);
}
long long Main( bool fl )
{
    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] = max(dp[i - 1][0], dp[i - 1][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];
        }
    }
    return max( dp[n - 1][0], dp[n - 1][1] );
}
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 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 568 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 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 784 KB Output is correct
7 Correct 3 ms 908 KB Output is correct
8 Correct 2 ms 908 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 3 ms 908 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 31944 KB Output is correct
2 Correct 5 ms 31944 KB Output is correct
3 Correct 273 ms 125932 KB Output is correct
4 Correct 5 ms 125932 KB Output is correct
5 Correct 18 ms 125932 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 784 KB Output is correct
7 Correct 3 ms 908 KB Output is correct
8 Correct 2 ms 908 KB Output is correct
9 Correct 3 ms 908 KB Output is correct
10 Correct 3 ms 908 KB Output is correct
11 Correct 66 ms 31944 KB Output is correct
12 Correct 5 ms 31944 KB Output is correct
13 Correct 273 ms 125932 KB Output is correct
14 Correct 5 ms 125932 KB Output is correct
15 Correct 18 ms 125932 KB Output is correct
16 Correct 304 ms 126048 KB Output is correct
17 Correct 163 ms 126048 KB Output is correct
18 Correct 252 ms 126048 KB Output is correct
19 Correct 219 ms 126048 KB Output is correct
20 Correct 254 ms 135068 KB Output is correct
21 Correct 189 ms 135068 KB Output is correct