Submission #197319

#TimeUsernameProblemLanguageResultExecution timeMemory
197319quocnguyen1012Split the sequence (APIO14_sequence)C++14
100 / 100
1104 ms81216 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; typedef long long ll; const int maxn = 1e5 + 5; ll f[2][maxn]; int opt[201][maxn]; int N, K; ll a[maxn]; bool Max(ll & a, ll b) { if (a <= b){ a = b; return true; } return false; } void calc(int lev, int mid, int L, int R) { f[1][mid] = -1e18; for (int i = L; i <= min(mid - 1, R); ++i){ ///cerr << a[i] * (a[mid] - a[i]) << '\n'; if (Max(f[1][mid], f[0][i] + a[i] * (a[mid] - a[i]))){ opt[lev][mid] = i; } } } void solve(int lev, int l, int r, int L, int R) { if (l > r) return; int mid = (l + r) / 2; calc(lev, mid, L, R); solve(lev, l, mid - 1, L, opt[lev][mid]); solve(lev, mid + 1, r, opt[lev][mid], R); } signed main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen("A.INP", "r")){ freopen("A.INP", "r", stdin); freopen("A.OUT", "w", stdout); } cin >> N >> K; for (int i = 1; i <= N; ++i){ cin >> a[i]; a[i] += a[i - 1]; } for (int i = 1; i <= K; ++i){ solve(i, 1, N, 1, N); for (int j = 0; j <= N; ++j){ f[0][j] = f[1][j]; } } cout << f[1][N] << '\n'; int n = N; for (int i = K; i >= 1; --i){ cout << opt[i][n] << ' '; n = opt[i][n]; } }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...