oj.uz

Submission #767098

# Submission time Handle Problem Language Result Execution time Memory
767098 2023-06-26T11:38:50 Z LucaIlie Homecoming (BOI18_homecoming) C++17
31 / 100
 1000 ms 169128 KB 
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const long long INF = 1e16;
const int MAX_SGT = 4e6 + 1;

struct SegTree {
    long long segTree[4 * MAX_SGT], lazy[4 * MAX_SGT];

    void init( int n ) {
        for ( int v = 0; v < 4 * n; v++ ) {
            segTree[v] = -INF;
            lazy[v] = 0;
        }
    }

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

    void update( int v, int l, int r, int lu, int ru, long long x ) {
        propag( v, l, r );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = x;
            propag( v, l, r );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    long long query( int v, int l, int r, int lq, int rq ) {
        propag( v, l, r );

        if ( l > rq || r < lq )
            return -INF;

        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        return max( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
    }
};

SegTree dp;
long long sumB[MAX_SGT], val[MAX_SGT];

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

    for ( int i = n; i <= n + k; i++ )
        sumB[i] = 0;
    for ( int i = n - 1; i >= 0; i-- )
        sumB[i] = sumB[i + 1] + b[i];

    for ( int take = 0; take <= 1; take++ ) {
        dp.init( n + k + 1 );
        if ( !take ) {
            long long s = 0;
            for ( int j = 0; j <= k; j++ ) {
                val[n + j] = -s;
                s += b[j];
            }
        } else {
            for ( int j = 0; j <= k; j++ )
                val[n + j] = 0;
        }
        for ( int j = 0; j <= k; j++ )
            dp.update( 0, 0, n + k, n + j, n + j, INF + val[n + j] );


        long long maxA = val[n + k];
        for ( int i = n - 1; i >= 0; i-- ) {
            val[i] = -INF;
            if ( i >= k * take ) {
                val[i] = max( dp.query( 0, 0, n + k, i + 1, i + k ), maxA );
                dp.update( 0, 0, n + k, i, i, INF + val[i] );
            }

            dp.update( 0, 0, n + k, i + 1, i + k - 1, -b[i] );
            maxA = max( maxA, val[i + k] - (sumB[i + 1] - sumB[i + k]) );
            maxA = maxA - b[i] + a[i];
        }

        ans = max( ans, dp.query( 0, 0, n + k, 0, k - 1 ) );
        ans = max( ans, maxA );
    }

    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 7 ms 868 KB Output is correct
10 Correct 2 ms 460 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 43944 KB Output is correct
2 Correct 28 ms 588 KB Output is correct
3 Execution timed out 1041 ms 169128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 7 ms 1108 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 7 ms 868 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 620 ms 43944 KB Output is correct
12 Correct 28 ms 588 KB Output is correct
13 Execution timed out 1041 ms 169128 KB Time limit exceeded
14 Halted 0 ms 0 KB -