Submission #956716

#	Time	Username	Problem	Language	Result	Execution time	Memory
956716		theStaticMind	Homecoming (BOI18_homecoming)	C++14	0 / 100	206 ms	39656 KiB

homecoming

#ifndef __HOMECOMING_H
#define __HOMECOMING_H
#include <bits/stdc++.h>
using namespace std;

struct CyclicPrefixSum {
    vector<int> pref;
    int N;
    CyclicPrefixSum(int N, vector<int>& 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<int>& A, vector<int>& 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<int>& A, int K) {
    vector<int> 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<int> 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 < K + 2; i++) {
        ans = max(ans, solver(N, K, vA, vB));
        shift(vA, 1);
        shift(vB, 1);
    }

    return ans;
}


#endif

Compilation message (stderr)

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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 18
• Subtask 3: 0 / 31
• Subtask 4: 0 / 38