#include <bits/stdc++.h>
#define int long long
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define Sz(x) (int)x.size()
using namespace std;
const int N = 1e5 + 5;
const int LOG1 = 47;
const int LOG2 = 17;
const int MXA = 1e14;
const int inf = INT_MAX;
struct tree {
int l, r;
int mx, pos;
};
int n, a[N], sz = 0, dp[N], last[N], pref[N];
tree t[N * LOG1 * LOG2];
void newnode() {
sz++;
t[sz].l = t[sz].r = -1;
t[sz].mx = t[sz].pos = 0;
}
void upd(int pos, int val, int val2, int v = 1, int tl = 1, int tr = MXA) {
if (tl == tr) {
if (val > t[v].mx) {
t[v].mx = val;
t[v].pos = val2;
}
return;
}
int mid = (tl + tr) / 2;
if (pos <= mid) {
if (t[v].l == -1) {
newnode();
t[v].l = sz;
}
upd(pos, val, val2, t[v].l, tl, mid);
}
else {
if (t[v].r == -1) {
newnode();
t[v].r = sz;
}
upd(pos, val, val2, t[v].r, mid + 1, tr);
}
if (t[t[v].l].mx > t[t[v].r].mx) {
t[v].mx = t[t[v].l].mx;
t[v].pos = t[t[v].l].pos;
}
else {
t[v].mx = t[t[v].r].mx;
t[v].pos = t[t[v].r].pos;
}
}
pair <int,int> merge(pair<int,int> p1, pair<int,int> p2) {
if (p1.fi > p2.fi) return p1;
return p2;
}
pair <int,int> get(int l, int r, int v = 1, int tl = 1, int tr = MXA) {
if (tl > r || l > tr || v == 0) return mp(0, 0);
if (tl >= l && tr <= r) return mp(t[v].mx, t[v].pos);
int mid = (tl + tr) / 2;
return merge(get(l, r, t[v].l, tl, mid), get(l, r, t[v].r, mid + 1, tr));
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pref[i] = pref[i - 1] + a[i];
}
newnode();
dp[1] = 1;
last[1] = a[1];
upd(a[1] + a[1], 1, 1);
for (int i = 2; i <= n; i++) {
pair <int,int> p = get(1, pref[i]);
if (p.se == 0) {
dp[i] = 1;
last[i] = pref[i];
}
else {
dp[i] = p.fi + 1;
last[i] = (pref[i] - pref[p.se]);
}
upd(pref[i] + last[i], dp[i], i);
}
cout << dp[n];
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tt = 1;
// cin >> tt;
while (tt--) {
solve();
cout << '\n';
}
}
컴파일 시 표준 에러 (stderr) 메시지
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x66): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x71): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x7c): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa0): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xab): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc8): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xf4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xfb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x101): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
