oj.uz

Submission #956722

# Submission time Handle Problem Language Result Execution time Memory
956722 2024-04-02T11:38:01 Z vjudge1 Homecoming (BOI18_homecoming) C++17
13 / 100
 1000 ms 47696 KB 
#ifndef __HOMECOMING_H
#define __HOMECOMING_H
#include <bits/stdc++.h>
using namespace std;

struct CyclicPrefixSum {
    vector<long long> pref;
    int N;
    CyclicPrefixSum(int N, vector<long long>& A) : N(N) {
        pref.resize(N);
        pref[0] = A[0];
        for(int i = 1; i < N; i++) {
            pref[i] = pref[i - 1] + A[i];
        }
    }
    long long query(int l, int r) {
        if(l <= r) {
            return pref[r] - (l == 0 ? 0 : pref[l - 1]);
        } else {
            return query(0, r) + query(l, N - 1);
        }
    }
};

long long solver(int N, int K, vector<long long>& A, vector<long long>& B) {
    
    CyclicPrefixSum prefA(N, A);
    CyclicPrefixSum prefB(N, B);

    vector<vector<long long>> dp(N, {0, 0});

    dp[0][0] = 0;
    dp[0][1] = A[0] - prefB.query(0, K - 1);

    for(int i = 1; i < N; i++) {
        dp[i][0] = max(
            dp[i-1][0],
            i >= K ? dp[i - K][1] : 0
        );
        if (i + K - 1 >= N) continue;
        dp[i][1] = max(
            dp[i-1][1] + A[i] - B[i + K - 1],
            dp[i-1][0] + A[i] - prefB.query(i, i + K - 1)
        );
    }

    return max(dp[N-1][0], dp[N-1][1]);

}

void shift(vector<long long>& A, int K) {
    vector<long long> B = A;
    for(int i = 0; i < A.size(); i++) {
        A[i] = B[(i + K) % A.size()];
    }
}

long long solve(int N, int K, int *A, int *B) {
    vector<long long> vA(N), vB(N);
    for(int i = 0; i < N; i++) {
        vA[i] = A[i];
        vB[i] = B[i];
    }

    long long ans = accumulate(A, A + N, 0ll) - accumulate(B, B + N, 0ll);
    for(int i = 0; i < N + 2; i++) {
        ans = max(ans, solver(N, K, vA, vB));
        shift(vA, 1);
        shift(vB, 1);
    }

    return ans;
}

#endif

Compilation message

homecoming.cpp: In function 'void shift(std::vector<long long int>&, int)':
homecoming.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0; i < A.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 11 ms 516 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 348 KB Output is correct
5 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 11 ms 516 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 348 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Execution timed out 1068 ms 1020 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 47696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 11 ms 516 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 12 ms 348 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Execution timed out 1068 ms 1020 KB Time limit exceeded
7 Halted 0 ms 0 KB -