oj.uz

Submission #853202

# Submission time Handle Problem Language Result Execution time Memory
853202 2023-09-23T15:56:02 Z faruk Homecoming (BOI18_homecoming) C++17
100 / 100
 318 ms 262144 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
#define mp make_pair
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const ll INF = 1e18;


ll n, k;

ll cmp1(pii a, pii b) {return a.first < b.first;}

ll solve(int N, int K, int *A, int *B) {
    n = N, k = K;
    vector<ll> cost(n);
    cost[0] = B[0];
    for (int i = 1; i < n; i++)
        cost[i] = (ll)B[i] + cost[i - 1];
    vector<vector<ll> > dp(n, vector<ll>(2, -INF));
    // take 1
    dp[0][1] = (ll)A[0] - cost[k - 1];
    for (ll i = 1; i < n; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        ll val_continue = dp[i - 1][1] + (ll)A[i];
        if (i + k - 1 < n)
            val_continue -= (ll)B[i + k - 1, i + k - 1];
        ll val_begin_new = dp[i - 1][0] + (ll)A[i] - (cost[min(i + k - 1, n - 1)] - cost[i - 1]);
        dp[i][1] = max(val_continue, val_begin_new);
    }

    ll out = max(dp[n - 1][0], dp[n - 1][1]);

    dp = vector<vector<ll> >(n, vector<ll>(2, -INF));
    dp[0][0] = 0;
    for (ll i = 1; i < n; i++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        ll val_continue = dp[i - 1][1] + (ll)A[i];
        val_continue -= (ll)B[(i + k - 1) % n];

        ll val_begin_new = dp[i - 1][0] + (ll)A[i] - (cost[min(i + k - 1, n - 1)] - cost[i - 1]);
        if (i + k - 1 >= n)
            val_begin_new -= cost[(i + k - 1) % n];
        dp[i][1] = max(val_continue, val_begin_new);
    }

    return max(out, max(dp[n - 1][0], dp[n - 1][1]));
}

Compilation message

homecoming.cpp: In function 'll solve(int, int, int*, int*)':
homecoming.cpp:31:41: warning: left operand of comma operator has no effect [-Wunused-value]
   31 |             val_continue -= (ll)B[i + k - 1, i + k - 1];
      |                                   ~~~~~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 63040 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 312 ms 262144 KB Output is correct
4 Correct 3 ms 3040 KB Output is correct
5 Correct 15 ms 4596 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 82 ms 63040 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 312 ms 262144 KB Output is correct
14 Correct 3 ms 3040 KB Output is correct
15 Correct 15 ms 4596 KB Output is correct
16 Correct 318 ms 262144 KB Output is correct
17 Correct 146 ms 40544 KB Output is correct
18 Correct 256 ms 41872 KB Output is correct
19 Correct 263 ms 146240 KB Output is correct
20 Correct 281 ms 262144 KB Output is correct
21 Correct 267 ms 144516 KB Output is correct