oj.uz

Submission #767012

# Submission time Handle Problem Language Result Execution time Memory
767012 2023-06-26T10:15:42 Z LucaIlie Homecoming (BOI18_homecoming) C++17
31 / 100
 324 ms 262144 KB 
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const long long INF = 1e16;
const int MAX_N = 2e6;
vector<long long> dp[MAX_N + 1];

long long solve( int n, int k, int a[], int b[] ) {
    long long ans = 0;

    for ( int i = 0; i <= n + 1; i++ )
        dp[i].resize( k + 1 );
    for ( int take = 0; take <= 1; take++ ) {
        if ( !take ) {
            dp[n][0] = 0;
            for ( int j = 1; j <= k; j++ )
                dp[n][j] = dp[n][j - 1] - b[j - 1];
        } else {
            for ( int j = 0; j <= k; j++ )
                dp[n][j] = 0;
        }

        for ( int i = n - 1; i >= 0; i-- ) {
            dp[i][0] = -INF;
            if ( i >= k * take ) {
                for ( int j = 0; j <= k; j++ )
                    dp[i][0] = max( dp[i][0], dp[i + 1][j] );
            }

            for ( int j = 1; j < k; j++ )
                dp[i][j] = dp[i + 1][j - 1] - b[i];

            dp[i][k] = max( dp[i + 1][k - 1], dp[i + 1][k] ) - b[i] + a[i];
        }

        for ( int j = 0; j <= k; j++ )
            ans = max( ans, dp[0][j] );
    }

    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47244 KB Output is correct
2 Correct 28 ms 48848 KB Output is correct
3 Correct 25 ms 47240 KB Output is correct
4 Correct 30 ms 47632 KB Output is correct
5 Correct 26 ms 47588 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47244 KB Output is correct
2 Correct 28 ms 48848 KB Output is correct
3 Correct 25 ms 47240 KB Output is correct
4 Correct 30 ms 47632 KB Output is correct
5 Correct 26 ms 47588 KB Output is correct
6 Correct 164 ms 243260 KB Output is correct
7 Correct 126 ms 194864 KB Output is correct
8 Correct 46 ms 69308 KB Output is correct
9 Correct 30 ms 51300 KB Output is correct
10 Correct 27 ms 47308 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 74824 KB Output is correct
2 Correct 32 ms 48784 KB Output is correct
3 Runtime error 324 ms 262144 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47244 KB Output is correct
2 Correct 28 ms 48848 KB Output is correct
3 Correct 25 ms 47240 KB Output is correct
4 Correct 30 ms 47632 KB Output is correct
5 Correct 26 ms 47588 KB Output is correct
6 Correct 164 ms 243260 KB Output is correct
7 Correct 126 ms 194864 KB Output is correct
8 Correct 46 ms 69308 KB Output is correct
9 Correct 30 ms 51300 KB Output is correct
10 Correct 27 ms 47308 KB Output is correct
11 Correct 86 ms 74824 KB Output is correct
12 Correct 32 ms 48784 KB Output is correct
13 Runtime error 324 ms 262144 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -