Educational Codeforces Round 123 (Rated for Div. 2) C. Increase Subarray Sums
- Time : O(n^2)
- Space : O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| #include <bits/stdc++.h>
#pragma optimization_level 3 #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #pragma GCC optimization ("unroll-loops")
struct PairHash {inline std::size_t operator()(const std::pair<int,int> & v) const {return v.first*31+v.second;}};
#define MAX_N 1010 #define INF 987654321 #define EPS 1e-9 #define ll long long #define pll pair<ll, ll> #define vpll vector<pll> #define vall3 vector<array<ll,3>> #define all3 array<ll,3> #define all5 array<ll,5> #define vall5 vector<all5> #define vll vector<ll> #define vs vector<string> #define usll unordered_set<ll> #define uspll unordered_set<pll, PairHash> #define vvs vector<vs> #define vvll vector<vll> #define all(a) begin(a), end(a)
using namespace std;
vll solve(vll& A, ll x) { ll n = A.size(); vll psum(n + 1); vll ma(n + 1, LLONG_MIN); vll res(n + 1); for(ll i = 0; i < n; i++) { psum[i + 1] = psum[i] + A[i]; for(ll j = 0; j <= i; j++) { ma[i-j+1] = max(ma[i-j+1], psum[i+1] - psum[j]); } } for(ll i = 0; i <= n; i++) { for(ll j = i; j <= n; j++) { res[i] = max(res[i], ma[j] + i * x); } if(i) res[i] = max(res[i], res[i-1]); } return res; }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; cin>>tc; for(ll i = 1; i <= tc; i++) { ll n, x; cin>>n>>x; vll A(n); for(ll j = 0; j < n; j++) cin>>A[j]; auto res = solve(A,x); for(auto& r : res)cout<<r<<' ';cout<<endl; } return 0; }
|