Aesthetic food Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 17

Build an AI-First Career, Master the Complete Skillset

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

Continuing from the hints:

Imagine we're trying to compute for k-th spice and our currect position is i, maintaining a max segment tree with the sum. dp[j][k-1]+c(j+1,i) in j-th cell where 0<=j<i. The answer for dp[n][k] is just a prefix query.
How do we move i the right? Let's denote i-th cake type as y.
Notice that the i->i+1 transition increases the segment tree values for all cells j such that there's no y in range [j+1,i] by one (since we've added a new distinct element). More formally, we increase all j's between the previous position of y plus one (or the beginning of the array if we haven't marked y before) to i.
Hence we got a lazy update segment tree and a simple prev[i] precalculation.

Time Complexity: O(N * A * log(N)) Space Complexity: O(N*A)