Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
MasterChef CodeChef Solution
Problem -MasterChef CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
MasterChef CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
typedef long long ll;
#define int long long
#define mod 1000000007
#define mod2 998244353
#define INF 2000000000000000000
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int,int>
#define vpi vector<pi>
#define forn(i, n) for(int i=0;i<n;i++)
#define all(x) begin(x), end(x)
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define gcd(x, y) __gcd(x, y)
#define f first
#define s second
int power(int a, int x, int m){
a=a%m;
int ans=1;
while(x){
if(x&1)ans=(ans*a)%m;
x=x>>1;
a=(a*a)%m;
}
return ans;
}
int knapsack(vi &a, vi &w, int weight){
int n=a.size();
vvi dp(n+1, vi(weight+1));
// debug(n, weight);
for(int i=1;i<=n;i++){
for(int j=1;j<=weight;j++){
if(w[i-1]<=j)dp[i][j]=max(dp[i][j], a[i-1]+dp[i-1][j-w[i-1]]);
dp[i][j]=max(dp[i][j], dp[i-1][j]);
}
}
return dp[n][weight];
}
void solve(){
int n, k, m; cin >> n >> k >> m;
vi arr(n);
vi ca, wa;
int sum=0;
forn(i, n){
cin >> arr[i];
sum+=arr[i];
if(arr[i] < 0)ca.pb(-arr[i]);
}
vvi judges;
vvi event;
forn(i, m){
int u, v, c;
cin >> u >> v >> c;
event.push_back({u, 1, c});
event.push_back({v+1, 0, c});
}
sort(all(event));
vi cost(n, INF);
multiset<int>mst;
int j=0;
for(int i=0;i<n;i++){
while(j<sz(event) and event[j][0]<=i+1){
if(event[j][1]==1){
mst.insert(event[j][2]);
}else{
mst.erase(mst.find(event[j][2]));
}
j++;
}
if(sz(mst))cost[i]=(*mst.begin());
}
for(int i=0;i<n;i++){
if(arr[i]<0)wa.pb(cost[i]);
}
int ans = sum + knapsack(ca, wa, k);
cout << ans << "\n";
// cout << "completed\n";
}
int32_t main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
cin.tie(0),cout.tie(0);
ios_base::sync_with_stdio(false);
int t=1;
cin>>t;
for(int i=1;i<=t;i++){
//cout<<"Case #"<<i<<": ";
solve();
}
}MasterChef CodeChef Solution in C++14
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const int oo = 1e9;
int n, k, m;
int a[N], st[4*N], mn[N];
ll dp[N][505];
void update(int id, int l, int r, int u, int v, int val){
if ( l > v || r < u ) return;
if ( u <= l && r <= v ){
st[id] = min(st[id], val);
return;
}
int mid = l + r >> 1;
update(id*2, l, mid, u, v, val);
update(id*2+1, mid+1, r, u, v, val);
}
int get(int id, int l, int r, int u){
if ( l > u || r < u ) return oo;
if ( l == r ) return st[id];
int mid = l + r >> 1;
return min({st[id], get(id*2, l, mid, u), get(id*2+1, mid+1, r, u)});
}
void solve(){
cin >> n >> k >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int i = 1; i <= 4*n; i ++) st[i] = oo;
for (int i = 1; i <= m; i ++){
int l, r, c;
cin >> l >> r >> c;
update(1, 1, n, l, r, c);
}
for (int i = 1; i <= n; i ++)
mn[i] = get(1, 1, n, i);
for (int i = 0; i <= n; i ++)
for (int j = 0; j <= k; j ++)
dp[i][j] = -1e15;
ll ans = -1e15;
dp[0][0] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= k; j ++){
dp[i][j] = dp[i-1][j] + a[i];
if ( j >= mn[i] && a[i] < 0 )
dp[i][j] = max(dp[i][j], dp[i-1][j-mn[i]]);
if ( i == n ) ans = max(ans, dp[i][j]);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if ( fopen("trash.inp", "r") ){
freopen("trash.inp", "r", stdin);
freopen("trash.out", "w", stdout);
}
int test;
cin >> test;
while ( test -- )
solve();
return 0;
}MasterChef CodeChef Solution in C
#include<stdio.h>
#include<stdlib.h>
inline long long int max(long long int a, long long int b)
{
return (a > b)? a : b;
}
inline long int Scan_f()
{
long int num = 0;
char c = getchar_unlocked();
int flag = 0;
while(!((c>='0' & c<='9') || c == '-'))
c=getchar_unlocked();
if(c == '-')
{
flag = 1;
c=getchar_unlocked();
}
while(c>='0' && c<='9')
{
num = (num<<1)+(num<<3)+c-'0';
c=getchar_unlocked();
}
if(flag==0)
return num;
else
return -1*num;
}
struct node
{
int left;
int right;
int cost;
}
query[100005];
int compare( const void * e1, const void * e2)
{
struct node *f = (struct node *) e1;
struct node *s = (struct node *) e2;
if(f->cost < s->cost)
return -1;
else if(f->cost > s->cost)
return 1;
else
return 0;
}
int main()
{
int t,n,k,m,i,j,p,cost[100005];
long long int arr[100005],c[505],sum;
scanf("%d",&t);
while(t--)
{
sum=0;
for(i=0;i<505;i++)
c[i]=0;
n=Scan_f(); k=Scan_f(); m=Scan_f();
for(i=0;i<n;i++)
{
arr[i]=Scan_f();
sum+=arr[i];
}
for(i=0;i<m;i++)
{
query[i].left=Scan_f(); query[i].right=Scan_f(); query[i].cost=Scan_f();
query[i].left--;
query[i].right--;
}
qsort(query, m,sizeof(struct node), compare);
p=0;
for(i=0; i<n; i++)
{
if(arr[i] < 0)
{
for(j=0; j<m; j++)
{
if( i>=query[j].left && i<=query[j].right )
{
arr[p] = -arr[i];
cost[p++] = query[j].cost;
break;
}
}
}
}
for(j=0;j<p;j++)
{
for(i=k-cost[j];i>=0;--i)
{
c[i + cost[j]] = max(c[i + cost[j]], c[i] + arr[j]);
}
}
sum = c[k]+sum;
printf("%lld\n",sum);
}
return 0;
} MasterChef CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.text.DecimalFormat;
class Main
{
/* static class pair{
long area;int idx;
pair(){}
pair(long a,int b)
{
area=a;
idx=b;
}
}
private static class Book {
int exercises;
String name;
int index;
public Book(){
this.index=0;
}
}*/
static class Pair implements Comparable<Pair>
{
long value;
long wt;
public Pair(long value, long wt)
{ this.value = value;
this.wt = wt;
}
@Override
public int compareTo (Pair ob)
{
return(Long.compare(this.value, ob.value));
}
}
static class master implements Comparable {
Integer l;
Integer r;
Integer cost;
public master(Integer l, Integer r, Integer cost) {
this.l = l;
this.r = r;
this.cost = cost;
}
@Override
public int compareTo(Object o) {
return Integer.compare(this.cost, ((master)o).cost);
}
}
/* static class Pair
{
int value,wt;
Pair(int value,int wt)
{this.value = value;this.wt=wt;}
}*/
/*static class masterComparator implements Comparator<master>{
public int compare(master p1, master p2) {
return Integer.compare(p2.cost, p1.cost);}
}
static class master {
int l,r,cost;
public master(int i,int j, int x){
this.l= i;
this.r=j;
this.cost=x;
}
}
*/
static class Triplet
{
int x[]=new int[3];
Triplet(int a,int b,int c)
{
this.x[0]=a;
this.x[1] =b;
this.x[2] = c;
}
}
static int days4=0;
static int all;
static long phi[]=new long[1000001];
static long ans[]=new long[1000001];
//static int tree[],sum[];
//public static long mod = 1000000007;
public static long [][] tempMatrix;
public static long max = (long) Math.pow(10, 9) + 7;
static StringBuilder res = new StringBuilder();
static long tree[],lazy[];
static long mod = 998244353;
public static int rootColor=0;
static boolean primes[]=new boolean[10000001];
private static final int MAXN = 5001;
private static final int MOD = 1000000007;
private static Modular modular_nCr = new Modular(MOD - 1);
private static Modular modular = new Modular(MOD);
private static final long[][] nCr = new long[MAXN][MAXN];
private static long bruteAns = 1;
static {
nCr[0][0] = 1;
for (int i = 1; i < MAXN; i++) {
nCr[i][0] = 1;
for (int j = 1; j <= i; j++) {
nCr[i][j] = modular_nCr.add(nCr[i - 1][j - 1], nCr[i - 1][j]);
}
}
}
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
FastReader in = new FastReader(System.in);
Scanner sc = new Scanner(System.in);
PrintWriter out=new PrintWriter(System.out);
//HashMap<Long, Long> h = new HashMap<Long, Long>();
TreeMap<Integer, Integer> h1 = new TreeMap<Integer, Integer>();
HashMap<Long, Long> h2 = new HashMap<Long, Long>();
//HashSet<Integer> s = new HashSet<Integer>();
HashSet<String> s1 = new HashSet<String>();
HashSet<String> s2 = new HashSet<String>();
// HashSet<Character> h2 = new HashSet<Character>();
//long t= in.nextLong();
// long t = in.nextLong();
//DecimalFormat df = new DecimalFormat("#,###,##0.000000");
boolean prime[]=new boolean[10000000];
//int p[]=new int[10000000];
//int k=1;
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;
for(int i=2;i<10000000;i++)
{
if(!prime[i])
continue;
// p[i]=k;
// k++;
for(long j=(long)i*i;j<10000000;j+=i)
prime[(int)j]=false;
}
long mod = 1000000007;
int t = in.nextInt() ;
while(t-->0)
{
long n = in.nextLong();
long k = in.nextLong();
long m = in.nextLong();
long[] a = new long[(int)n];
long sum=0;
ArrayList<Pair> list = new ArrayList<Pair>();
for(int i=0;i<n;i++)
{
a[i] = in.nextInt();
sum = sum+a[i];
}
long[] min = new long[(int)n+1];
tree=new long[(int)n<<2];
lazy=new long[(int)n<<2];
Arrays.fill(tree,1000);
Arrays.fill(lazy,1000);
for(int i=0;i<m;i++)
{
long l = in.nextLong();
long r = in.nextLong();
long cost = in.nextLong();
update(0,n-1,l-1,r-1,cost,0);
}
/*
for(int i=0;i<=n;i++)
{
System.out.println(min[i]);
}
*/
int j=0;
long ans =0;
for(int i=0;i<n;i++)
{
if(a[i]<0)
{
list.add(new Pair(Math.abs(a[i]),get(0,(int)n-1,i,i,0)));
}
}
Collections.sort(list);
/* for(int i=0;i<list.size();i++)
{
System.out.println(list.get(i).value+" "+list.get(i).wt);
}*/
long[][] dp = new long[list.size()+1][(int)k+1];
for(int i=0;i<=list.size();i++)
{
for(j=0;j<=k;j++)
{
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (list.get(i - 1).wt <= j)
dp[i][j] = Math.max(list.get(i - 1).value + dp[i - 1][j - (int)list.get(i - 1).wt], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
// System.out.println(dp[i][j]);
}
}
/* for(int i=list.size()-1;i>0;i--)
{
if(dp[i][(int)k]>0)
{
ans = dp[i][(int)k];
break;
}
}*/
System.out.println(sum+dp[list.size()][(int)k]);
}
}
static void update(long st,long end,long qs,long qe,long cost,long node)
{
if(lazy[(int)node]!=1000)
{
tree[(int)node]=(long)Math.min(tree[(int)node],lazy[(int)node]);
if(st!=end)
{
lazy[(int)node*2 +1]=(long)Math.min(lazy[(int)node*2 +1],lazy[(int)node]);
lazy[(int)node*2 +2]=(long)Math.min(lazy[(int)node*2 +2],lazy[(int)node]);
}
lazy[(int)node]=1000;
}
if((st > end) || (st > qe) || (end < qs))
return;
if(st>=qs && end<=qe)
{tree[(int)node]=(int)Math.min(tree[(int)node],cost);
if(st!=end)
{
lazy[(int)node*2 +1]=(long)Math.min(lazy[(int)node*2 +1],cost);
lazy[(int)node*2 +2]=(long)Math.min(lazy[(int)node*2 +2],cost);
}
return;
}
long mid=(st+end)/2;
update(st,mid,qs,qe,cost,node*2 +1);
update(mid+1,end,qs,qe,cost,node*2 +2);
tree[(int)node]=(long)Math.min(tree[(int)node*2 +1],tree[(int)node*2 +2]);
}
static long get(int st,int end,int qs,int qe,int node)
{
if(lazy[node]!=1000)
{
tree[node]=(int)Math.min(tree[node],lazy[node]);
if(st!=end)
{
lazy[node*2 +1]=(int)Math.min(lazy[node*2 +1],lazy[node]);
lazy[node*2 +2]=(int)Math.min(lazy[node*2 +2],lazy[node]);
}
lazy[node]=1000;
}
if((st > end) || (st > qe) || (end < qs))
return 1000;
if(st>=qs && end<=qe)
return tree[node];
int mid=(st+end)/2;
return (int)Math.min(get(st,mid,qs,qe,node*2 +1),get(mid+1,end,qs,qe,node*2 +2));
}/*
static void update(long[] min, long l , long r , long cost)
{
for(long i=l;i<=r;i++)
{
if(cost<min[(int)i])
{
min[(int)i] = cost;
}
}
}*/
static long power(long x, long y, long p)
{
long res = 1;
x = x % p;
if (x == 0) return 0;
while (y > 0)
{
if((y & 1)==1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
} return res;
} static int gcd(int n, int m) {
if(m == 0) return n;
return gcd(m, n % m);
}
public static class Modular {
private int MOD;
Modular(int MOD) {
this.MOD = MOD;
}
public long add(long a, long b) {
return (a + b) % MOD;
}
public long sub(long a, long b) {
return (a - b + MOD) % MOD;
}
public long mul(long a, long b) {
return (a * b) % MOD;
}
public long div(long a, long b) {
return mul(a, inverseEuler(b));
}
/* This function calculates (a^b)%MOD */
public long power(long a, long b) {
long x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);
if (x >= MOD) x %= MOD;
}
y = (y * y);
if (y >= MOD) y %= MOD;
b /= 2;}
return x;
}
/* Modular Multiplicative Inverse
Using Euler's Theorem
a^(phi(m)) = 1 (mod m)
a^(-1) = a^(m-2) (mod m) */
public long inverseEuler(long n) {
return power(n, MOD - 2);
}
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;FastReader(InputStream is) {
in = is;
} int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) { return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}String nextLine() throws IOException {
int c;for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c != 10 && c != 13; c = scan()) {
sb.append((char) c);
} return sb.toString();
}char nextChar() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
return (char) c;
} int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan(); }
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
}
}MasterChef CodeChef Solution in GO
package main
import (
"bufio"
"container/heap"
"fmt"
"math"
"os"
"sort"
)
var in = bufio.NewScanner(os.Stdin)
func readInt() int64 {
if !in.Scan() {
panic(in.Err())
}
res := int64(0)
neg := false
for _, b := range in.Bytes() {
if b == '-' {
neg = true
continue
}
res = res*10 + int64(b-'0')
}
if neg {
res *= -1
}
return res
}
func main() {
in.Split(bufio.ScanWords)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
for t := readInt(); t > 0; t-- {
fmt.Fprintln(out, solve())
}
}
func save(cost []int, ratings []int64, budget int) int64 {
dp := make([]int64, budget+1)
for i := range ratings {
v := -ratings[i]
if v <= 0 {
continue
}
c := cost[i]
for j := budget; j >= c; j-- {
if dp[j] < dp[j-c]+v {
dp[j] = dp[j-c] + v
}
}
}
res := int64(0)
for _, v := range dp[1:] {
if res < v {
res = v
}
}
return res
}
type addRem struct {
pos, price int
add bool
}
type byPos []addRem
func (s byPos) Len() int { return len(s) }
func (s byPos) Less(i, j int) bool { return s[i].pos < s[j].pos }
func (s byPos) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
func solve() int64 {
ratingSum := int64(0)
n, k, m := int(readInt()), int(readInt()), int(readInt())
ratings := make([]int64, n)
for i := range ratings {
ratings[i] = readInt()
ratingSum += ratings[i]
}
ars := make([]addRem, 2*m+2)
for i := 0; i < m; i++ {
l, r, c := int(readInt()), int(readInt()), int(readInt())
ars[i*2] = addRem{l - 1, c, true}
ars[i*2+1] = addRem{r, c, false}
}
ars[2*m] = addRem{0, math.MaxInt32, true}
ars[2*m+1] = addRem{n + 1, math.MaxInt32, false}
sort.Sort(byPos(ars))
var h, toRemove intHeap
cost := make([]int, 0, n)
for _, ar := range ars {
for len(cost) < ar.pos {
cost = append(cost, h[0])
}
if ar.add {
heap.Push(&h, ar.price)
} else {
heap.Push(&toRemove, ar.price)
}
for len(toRemove) > 0 && h[0] == toRemove[0] {
heap.Pop(&h)
heap.Pop(&toRemove)
}
}
return ratingSum + save(cost, ratings, k)
}
type intHeap []int
func (h intHeap) Len() int { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h intHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *intHeap) Pop() interface{} {
n := len(*h)
x := (*h)[n-1]
(*h) = (*h)[:n-1]
return x
}MasterChef CodeChef Solution Review:
In our experience, we suggest you solve this MasterChef CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the MasterChef CodeChef Solution.
Conclusion:
I hope this MasterChef CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
