Submission #345357

#	Time	Username	Problem	Language	Result	Execution time	Memory
345357		mohamedsobhi777	Hacker (BOI15_hac)	C++14	100 / 100	882 ms	190796 KiB

hac

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e6 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

__int128 read()
{
       __int128 x = 0, f = 1;
       char ch = getchar();
       while (ch < '0' || ch > '9')
       {
              if (ch == '-')
                     f = -1;
              ch = getchar();
       }
       while (ch >= '0' && ch <= '9')
       {
              x = x * 10 + ch - '0';
              ch = getchar();
       }
       return x * f;
}
void print(__int128 x)
{
       if (x < 0)
       {
              putchar('-');
              x = -x;
       }
       if (x > 9)
              print(x / 10);
       putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }

int n;

multiset<ll> add[N], rem[N];

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);

       cin >> n;
       vll a(n);
       for (auto &u : a)
              cin >> u;
       ll ans = 0;
       int t = (n + 1) / 2;
       for (int i = 0; i < n; ++i)
              a.pb(a[i]);
       for (int i = 1; i < 2 * n; ++i)
              a[i] += a[i - 1];
       auto get = [&](int l, int r) -> ll {
              return a[r] - (l ? a[l - 1] : 0);
       };
       vll dp(n, 1e18);
       for (int i = t - 1; i < 2 * n; ++i)
       {
              add[i - t + 1].insert(get(i - t + 1, i));
              rem[i + 1].insert(get(i - t + 1, i));
       }
       multiset<ll> mul;
       for (int i = 0; i < 2 * n; ++i)
       {
              for (auto u : add[i])
                     mul.insert(u);
              for (auto u : rem[i])
                     mul.erase(mul.find(u));
              if (sz(mul))
                     dp[i % n] = min(dp[i % n], *(mul.begin()));
       }
       cout << *max_element(all(dp));
       return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:93:11: warning: unused variable 'ans' [-Wunused-variable]
   93 |        ll ans = 0;
      |           ^~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40