Submission #1075330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075330		vjudge1	Candies (JOI18_candies)	C++17	100 / 100	3504 ms	319800 KiB

candies

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

// smawck for max
template<class F>
std::vector<int> smawck(F f, const std::vector<int> &rows, const std::vector<int> &cols) {
    std::vector<int> ans(rows.size(), -1);
    if((int) std::max(rows.size(), cols.size()) <= 2) {
        for(int i = 0; i < (int) rows.size(); i++) {
            for(auto j : cols) {
                if(ans[i] == -1 || f(rows[i], ans[i], j)) {
                    ans[i] = j;
                }
            }
        }
    } else if(rows.size() < cols.size()) {
        // reduce
        std::vector<int> st;
        for(int j : cols) {
            while(1) {
                if(st.empty()) {
                    st.push_back(j);
                    break;
                } else if(f(rows[(int) st.size() - 1], st.back(), j)) {
                    st.pop_back();
                } else if(st.size() < rows.size()) {
                    st.push_back(j);
                    break;
                } else {
                    break;
                }
            }
        }
        ans = smawck(f, rows, st);
    } else {
        std::vector<int> newRows;
        for(int i = 1; i < (int) rows.size(); i += 2) {
            newRows.push_back(rows[i]);
        }
        auto otherAns = smawck(f, newRows, cols);
        for(int i = 0; i < (int) newRows.size(); i++) {
            ans[2*i+1] = otherAns[i];
        }
        for(int i = 0, l = 0, r = 0; i < (int) rows.size(); i += 2) {
            if(i+1 == (int) rows.size()) r = (int) cols.size();
            while(r < (int) cols.size() && cols[r] <= ans[i+1]) r++;
            ans[i] = cols[l++];
            for(; l < r; l++) {
                if(f(rows[i], ans[i], cols[l])) {
                    ans[i] = cols[l];
                }
            }
            l--;
        }
    }
    return ans;
}

// max smawck
// F(i, j, k) checks if M[i][j] <= M[i][k]
// another interpretations is: 
// F(i, j, k) checks if M[i][k] is at least as good as M[i][j]
// higher == better
// when comparing 2 columns as vectors
// for j < k, column j can start better than column k
// as soon as column k is at least as good, it's always at least as good
template<class F>
std::vector<int> smawck(F f, int n, int m) {
    std::vector<int> rows(n), cols(m);
    for(int i = 0; i < n; i++) rows[i] = i;
    for(int i = 0; i < m; i++) cols[i] = i;
    return smawck(f, rows, cols);
}

template<class T>
void MaxConvolutionWithConvexShape(const std::vector<T> &anyShape, const std::vector<T> &convexShape, std::vector<T> &ans) {
    if((int) convexShape.size() <= 1) {
        ans = anyShape;
        return;
    }
    // if(anyShape.empty()) anyShape.push_back(0);
    int n = (int) anyShape.size(), m = (int) convexShape.size();
    auto function = [&](int i, int j) {
        return anyShape[j] + convexShape[i-j];
    };
    auto comparator = [&](int i, int j, int k) {
        if(i < k) return false;
        if(i - j >= m) return true;
        return function(i, j) <= function(i, k);
    };
    const std::vector<int> best = smawck(comparator, n + m - 1, n);
    // ans.resize(n + m - 1);
    for(int i = 0; i < n + m - 1; i++) {
        ans[i] = max(ans[i], function(i, best[i]));
    }
    // return ans;
}

void solve() {
    int n;
    cin >> n;

    vector<i64> a(n);
    for (auto &val : a) cin >> val;


    // int sum = 0;
    // auto dfs = [&](auto self, int l, int r) -> void {
    //     if (mp.find(pair{l, r}) != mp.end()) return;
    //     mp[{l, r}] = 1;
    //     if (r - l == 1) { mp[{l, r}]++; return; }
    //     if (r - l == 2) { mp[{l, r}]++; return; }
    //     if (r - l == 3) { mp[{l, r}]++; return; }
    //     // cout << l << " " << r << endl;
    //     int mr = (l + r) >> 1, ml = mr - 1;
    //     self(self, l, ml); self(self, ml + 1, r);
    //     self(self, l, mr); self(self, mr + 1, r);
    // };
    // dfs(dfs, 0, n);
    // cout << sum << endl;

    // vector<int> A = {-2, -1, -2};
    // vector<int> B = {-2, -0, -1, -3};
    // vector<int> ans;
    // MaxConvolutionWithConvexShape(A, B, ans);
    // for (auto val : ans) cout << val << " ";
    // cout << endl;
    // return;

    map<pair<int, int>, vector<i64>> mp;
    auto dfs = [&](auto self, int l, int r) -> void {
        if (r - l == 1) {
            mp[{l, r}] = {0, *max_element(a.begin() + l, a.begin() + r)};
            return;
        }
        if (r - l == 2) {
            mp[{l, r}] = {0, *max_element(a.begin() + l, a.begin() + r)};
            return;
        }
        if (r - l == 3) {
            mp[{l, r}] = {0, *max_element(a.begin() + l, a.begin() + r), a[l] + a[l + 2]};
            return;
        }
        mp[{l, r}].resize(((r - l + 1) >> 1) + 1);

        int mr = (l + r) >> 1, ml = mr - 1;

        if (mp.find({l, ml}) == mp.end()) self(self, l, ml);
        if (mp.find({ml + 1, r}) == mp.end()) self(self, ml + 1, r);
        MaxConvolutionWithConvexShape(mp[{l, ml}], mp[{ml + 1, r}], mp[{l, r}]);

        if (mp.find({l, mr}) == mp.end()) self(self, l, mr);
        if (mp.find({mr + 1, r}) == mp.end()) self(self, mr + 1, r);
        MaxConvolutionWithConvexShape(mp[{l, mr}], mp[{mr + 1, r}], mp[{l, r}]);

        return;
    };
    dfs(dfs, 0, n);

    mp[{0, n}].erase(mp[{0, n}].begin());
    for (auto val : mp[{0, n}]) cout << val << endl;
}

signed main() {

    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
candies.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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