oj.uz

Submission #767014

# Submission time Handle Problem Language Result Execution time Memory
767014 2023-06-26T10:16:14 Z LucaIlie Homecoming (BOI18_homecoming) C++17
62 / 100
 213 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; 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 24 ms 47308 KB Output is correct
2 Correct 26 ms 48768 KB Output is correct
3 Correct 26 ms 47212 KB Output is correct
4 Correct 25 ms 47628 KB Output is correct
5 Correct 30 ms 47532 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47308 KB Output is correct
2 Correct 26 ms 48768 KB Output is correct
3 Correct 26 ms 47212 KB Output is correct
4 Correct 25 ms 47628 KB Output is correct
5 Correct 30 ms 47532 KB Output is correct
6 Correct 147 ms 243040 KB Output is correct
7 Correct 126 ms 194732 KB Output is correct
8 Correct 46 ms 69204 KB Output is correct
9 Correct 29 ms 51216 KB Output is correct
10 Correct 29 ms 47316 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 74572 KB Output is correct
2 Correct 31 ms 48228 KB Output is correct
3 Correct 213 ms 125808 KB Output is correct
4 Correct 40 ms 63684 KB Output is correct
5 Correct 36 ms 52296 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47308 KB Output is correct
2 Correct 26 ms 48768 KB Output is correct
3 Correct 26 ms 47212 KB Output is correct
4 Correct 25 ms 47628 KB Output is correct
5 Correct 30 ms 47532 KB Output is correct
6 Correct 147 ms 243040 KB Output is correct
7 Correct 126 ms 194732 KB Output is correct
8 Correct 46 ms 69204 KB Output is correct
9 Correct 29 ms 51216 KB Output is correct
10 Correct 29 ms 47316 KB Output is correct
11 Correct 71 ms 74572 KB Output is correct
12 Correct 31 ms 48228 KB Output is correct
13 Correct 213 ms 125808 KB Output is correct
14 Correct 40 ms 63684 KB Output is correct
15 Correct 36 ms 52296 KB Output is correct
16 Runtime error 180 ms 262144 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -