Submission #639870

#TimeUsernameProblemLanguageResultExecution timeMemory
639870bojackduySplit the sequence (APIO14_sequence)C++14
Compilation error
0 ms0 KiB
#include <iostream> #include <queue> #include <stack> #include <algorithm> #include <string.h> #include <functional> #define int long long #define size() size() * 1ll #define all(x) (x).begin(), (x).end() #define allr(x, sz) (x) + 1, (x) + 1 + sz #define pb push_back #define pii pair<int, int> // #define fi first // #define se second #define MASK(x) (1LL << (x)) #define BIT(x,i) (((x) >> (i)) & 1) #define numbit(x) __builtin_popcountll(x) using namespace std; const int N = 1e6 + 1; const int M = 1e3 + 1; const long long mod = 1e9 + 7; const long long oo = 1e18 + 7; typedef vector<int> vi; typedef vector<pii> vii; typedef long long ll; template<class t> bool mini(t &x,t y) { if (y < x) { x = y; return 1; } return 0; } template<class t> bool maxi(t &x,t y) { if (x < y) { x = y; return 1; } return 0; } void file() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen(task".inp", "r", stdin); // freopen(task".out", "w", stdout); return ; } const int K = 202; int n, k; int a[N], suf[N], dp[N][K], trace[N][K]; void dnc(int z, int l, int r, int u, int v) { if (l > r) return ; int mid = l + r >> 1; int g = u; for (int i = u; i <= v; i++) { if (maxi(dp[mid][z], dp[i][z - 1] + suf[i] * suf[mid] - suf[mid] * suf[mid])) { trace[mid][z] = i; g = i; } } dnc(z, l, mid - 1, u, g); dnc(z, mid + 1, r, g, v); } void solve(int test = -1) { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } n++; k++; for (int i = n; i >= 1; i--) { suf[i] = suf[i + 1] + a[i]; } for (int z = 1; z <= k; z++) { dnc(z, z + 1, n, z, n); // for (int i = 1; i <= n; i++) dp[i][z] = dp[g[i]][z - 1] + suf[g[i]] * suf[i] - suf[i] * suf[i]; } cout << dp[n][k] << '\n'; while (k > 1) { n = trace[n][k]; cout << n - 1 << ' '; k--; } } int32_t main() { file(); int T = 1; // cin >> T; for (int i = 1; i <= T; i++) { solve(i); } return 0; } /* 7 3 4 1 3 4 0 2 3 */

Compilation message (stderr)

sequence.cpp: In function 'void dnc(long long int, long long int, long long int, long long int, long long int)':
sequence.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = l + r >> 1;
      |               ~~^~~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status