Submission #1075333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075333		daoquanglinh2007	Candies (JOI18_candies)	C++17	100 / 100	2025 ms	318728 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;

template<class T>
void MaxConvolutionWith2ConvexShape(const std::vector<T> &A, const std::vector<T> &B, std::vector<T> &ans) {
    int n = isz(A), m = isz(B);
    int ptrA = 0, ptrB = 0;
    for (int i = 0; i < n + m - 1; ++i) {
        ans[i] = max(ans[i], A[ptrA] + B[ptrB]);
        if (ptrA == n - 1) ++ptrB;
        else if (ptrB == m - 1) ++ptrA;
        else {
            if (A[ptrA + 1] - A[ptrA] > B[ptrB + 1] - B[ptrB]) ++ptrA;
            else ++ptrB;
        }
    }
}
 
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);
        MaxConvolutionWith2ConvexShape(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);
        MaxConvolutionWith2ConvexShape(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:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
candies.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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