Submission #1089838

#TimeUsernameProblemLanguageResultExecution timeMemory
1089838PekibanCandies (JOI18_candies)C++17
8 / 100
5019 ms5704 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; using ll = long long; #define pb push_back vector<ll> mxconv(vector<ll> &a, vector<ll> &b) { int n = a.size(), m = b.size(); vector<ll> c(n+m, -1e15 ); 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<ll> dq(vector<ll> &a) { int n = a.size(); if (n == 0) return {0}; if (n == 1) return {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]); reverse(R.begin(), R.end()); auto A = dq(L); L.pop_back(); auto B = dq(L); auto C = dq(R); R.pop_back(); auto D = dq(R); auto E = mxconv(A, D); auto F = mxconv(C, B); for (int i = 0; i < E.size(); ++i) E[i] = max(E[i], F[i]); return E; } // proof by ac lol 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 << ans[i] << '\n'; } }

Compilation message (stderr)

candies.cpp: In function 'std::vector<long long int> dq(std::vector<long long int>&)':
candies.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < E.size(); ++i)  E[i] = max(E[i], F[i]);
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...