A nice idea with memory optimization for Knapsack dp
// Link: http://www.codechef.com/JULY15/problems/MCHEF/ /**************************************************************** ▄█ █▄ ▄████████ ▄████████ ▄█ ▀█████████▄ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ ███ █▀ ███ ███ ███ ▄███▄▄▄▄███▄▄ ███ ███ ███ ███ ▄███▄▄▄██▀ ▀▀███▀▀▀▀███▀ ▀███████████ ▀███████████ ███ ▀▀███▀▀▀██▄ ███ ███ ███ ███ ███ ███ ███ ██▄ ███ ███ ███ ███ ▄█ ███ ███ ███ ███ ███ █▀ ███ █▀ ▄████████▀ █▀ ▄█████████▀ ****************************************************************/ #include<bits/stdc++.h> #define FOR(i, s, e) for(int i=s; i<e; i++) #define loop(i, n) FOR(i, 0, n) #define sf scanf #define pf printf #define pb push_back #define MP make_pair #define fr first #define sc second #define ll long long #define dd double #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define mem(ara, value) memset(ara, value, sizeof(ara)) #define paii pair<int, int> #define pall pair<ll, ll> #define SZ(a) int(a.size()) #define read(nm) freopen(nm, "r", stdin) #define write(nm) freopen(nm, "w", stdout) #define take(args...) asdf,args #define dump(x) cerr<<#x<<" = "<<x<<endl #define debug(args...) cerr,args; cerr<<endl; using namespace std; template<typename T> ostream& operator<<(ostream& output, vector<T>&v) { output<<"[ "; if(SZ(v)) { output<<v[0]; } FOR(i, 1, SZ(v)) { output<<", "<<v[i]; } output<<" ]"; return output; } template<typename T1, typename T2> ostream& operator<<(ostream& output, pair<T1, T2>&p) { output<<"( "<<p.fr<<", "<<p.sc<<" )"; return output; } template<typename T> ostream& operator,(ostream& output, T x) { output<<x<<" "; return output; } struct ASDF{ ASDF& operator,(int &a) { sf("%d", &a); return *this; } ASDF& operator,(long int &a){ sf("%ld", &a); return *this; } ASDF& operator,(long long int &a){ sf("%lld", &a); return *this; } ASDF& operator,(char &c){ sf("%c", &c); return *this; } ASDF& operator,(double &d){ sf("%lf", &d); return *this; } template<typename T> ASDF& operator,(T &a){ cin>>a; return *this; } }asdf; //Header ends here #define MAXX 100007 #define INF 16843009 int N, M; int K; ll ara[MAXX]; int L, R, C; int sum[4*MAXX]; ll dp[507]; void update(int idx, int st, int ed, int i, int j, int val) { if(st == i && ed == j) { sum[idx] = min(sum[idx], val); return; } int l = idx*2; int r = l + 1; int mid = (st + ed)/2; sum[l] = min(sum[l], sum[idx]); sum[r] = min(sum[r], sum[idx]); sum[idx] = INF; if(j <= mid) { update(l, st, mid, i, j, val); } else if(mid < i) { update(r, mid+1, ed, i, j, val); } else { update(l, st, mid, i, mid, val); update(r, mid+1, ed, mid+1, j, val); } } int get(int idx, int st, int ed, int pos) { if(st == ed) { return sum[idx]; } int l = idx*2; int r = l + 1; int mid = (st + ed)/2; if(sum[idx] != INF) { sum[l] = min(sum[l], sum[idx]); sum[r] = min(sum[r], sum[idx]); sum[idx] = INF; } if(pos <= mid) { return get(l, st, mid, pos); } else { return get(r, mid+1, ed, pos); } } void init() { mem(sum, 1); mem(dp, 0); } int main() { //init(); cout<<sum[0]; int kases; take(kases); while(kases--) { init(); take(N, K, M); ll s = 0; loop(i, N) { take(ara[i]); s += ara[i]; } loop(i, M) { take(L, R, C); update(1, 0, N-1, L-1, R-1, C); } //cerr<<"DONE"<<endl; loop(i, N) { if(ara[i] < 0) { ll tmp = -ara[i]; //dump(tmp); C = get(1, 0, N-1, i); //dump(C); for(int pos=K; pos>=0; pos--) { if(pos + C <= K) { dp[pos + C] = max(dp[pos + C], dp[pos] + tmp ); } } } } cout<< s + dp[K]<<endl; }
}