Submission #1089833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089833		Pekiban	Candies (JOI18_candies)	C++17	100 / 100	275 ms	16896 KiB

candies

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back

const ll inf = 1e15;
vector<ll> mxconv(vector<ll> &a, vector<ll> &b) {
    int n = a.size(), m = b.size();
    vector<ll> c(n+m-1);
    c[0] = 0;
    int i = 1, j = 1;
    while (i < n || j < m) {
        if (i == n) ++j;
        else if (j == m)    ++i;
        else {
            if (a[i] - a[i-1] > b[j] - b[j-1])  ++i;
            else    ++j;
        }
        c[i+j-2] = a[i-1] + b[j-1];
    }
    return c;
}
vector<vector<vector<ll>>> dq(vector<ll> &a) { // dp[i][b1][b2] = uzmes ih i b1 = da li uzmes poslednji b2 = da li uzmes prvi
    int n = a.size();
    if (n == 0) return {{{{0}, {0}}}, {{{0}, {0}}}};
    if (n == 1) return {{{{0, -inf}, {0, -inf}}}, {{{0, -inf}, {0, a[0]}}}};
    vector<ll> L, R;
    for (int i = 0; i < n/2; ++i)   L.pb(a[i]);
    for (int i = n/2; i < n; ++i)   R.pb(a[i]);
    auto A = dq(L), B = dq(R);
    vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(2, vector<ll>(1 + (n+1)/2, -inf)));
    for (int X = 0; X < 2; ++X) {
        for (int Y = 0; Y < 2; ++Y) {
            auto t1 = mxconv(A[X][0], B[0][Y]);
            auto t2 = mxconv(A[X][1], B[0][Y]);
            auto t3 = mxconv(A[X][0], B[1][Y]);
            for (int i = 0; i <= (n+1)/2; ++i) {
                dp[X][Y][i] = max({
                (i < t1.size() ? t1[i] : -inf), 
                (i < t2.size() ? t2[i] : -inf), 
                (i < t3.size() ? t3[i] : -inf)});
            }
        }
    }
    return dp;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
	vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
	auto ans = dq(a);
	for (int i = 1; i <= (n+1)/2; ++i) {
		cout << max({ans[0][0][i], ans[0][1][i], ans[1][1][i], ans[1][0][i]}) << '\n';
	}
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<std::vector<std::vector<long long int> > > dq(std::vector<long long int>&)':
candies.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 (i < t1.size() ? t1[i] : -inf),
      |                  ~~^~~~~~~~~~~
candies.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                 (i < t2.size() ? t2[i] : -inf),
      |                  ~~^~~~~~~~~~~
candies.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |                 (i < t3.size() ? t3[i] : -inf)});
      |                  ~~^~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92