F - Diversity
Source: atcoder
Difficulty: 525

Problem Statement
There are
N
products for sale in a store. The
i
-th product has a price of
P_i
yen, a utility value of
U_i
, and a color
C_i
.
You will choose some subset of these
N
products to buy (possibly none). The total price of the chosen products must be at most
X
yen.
Your satisfaction is
S + T \times K
, where
S
is the sum of utilities of the chosen products, and
T
is the number of distinct colors among the chosen products. Here,
K
is a given constant.
You will choose products to maximize your satisfaction. Find the maximized satisfaction.
Constraints
1 \leq N \leq 500
1 \leq X \leq 50000
1 \leq K \leq 10^9
1 \leq P_i \leq X
(1 \leq i \leq N)
1 \leq U_i \leq 10^9
(1 \leq i \leq N)
1 \leq C_i \leq N
(1 \leq i \leq N)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
X
K
P_1
U_1
C_1
P_2
U_2
C_2
\vdots
P_N
U_N
C_N
Output
Print the answer.
Sample Input 1
3 10 5
1 3 1
7 4 2
4 5 1
Sample Output 1
17
If you buy the 1st and 2nd products, the total utility
S
is
7
, and the number of distinct colors
T
is
2
. Thus, your satisfaction is
7 + 2 \times 5 = 17
. No purchase plan makes your satisfaction
18
or greater, so the answer is
17
.
Sample Input 2
5 30 3
5 4 3
11 20 1
9 10 4
7 5 2
16 15 4
Sample Output 2
44
If you buy the 2nd, 3rd, and 4th products, the total utility
S
is
35
, and the number of distinct colors
T
is
3
. Thus, your satisfaction is
35 + 3 \times 3 = 44
. No purchase plan makes your satisfaction
45
or greater, so the answer is
44
.
Sample Input 3
22 75 6426
9 309 9
5 470 5
17 481 12
27 352 14
1 191 18
7 353 20
9 99 15
20 401 17
46 434 19
11 459 22
10 317 19
15 440 18
17 438 19
25 461 22
5 320 22
1 476 21
11 315 3
8 112 9
11 438 13
19 362 8
10 422 13
10 152 21
Sample Output 3
67717

C++ solution:
#include <iostream>
#include <vector>
#include <utility>

using namespace std;
using ll = long long;
using Data = pair<ll, ll>;

int main(void) {
    int N, X, K;
    cin >> N >> X >> K;

    // c別のP,Uを管理する
    vector<vector<Data>> g(N+1);
    for (int i = 0; i < N; i++) {
        ll p, u, c;
        cin >> p >> u >> c;
        c--;
        g[c].emplace_back(p, u);
    }

    const ll INF = -2e18;
    vector<ll> dp(X + 1,INF);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        vector<ll> next = dp;
        for (int pi = 0; pi < g[i].size(); pi++) {
            auto [p, u] = g[i][pi];
            for (int x = X; x >= p; x--) {
                if (dp[x - p] != INF) {
                    next[x] = max(next[x], dp[x-p] + u + K);
                }

                if (next[x - p] != INF) {
                    next[x] = max(next[x], next[x-p] + u);
                }
            }
        }
        swap(dp, next);
    }

    ll ans = 0;
    for (int x = 0; x <= X; x++) {
        ans = max(ans, dp[x]);
    }
    cout << ans << endl;
    return 0;
}

Go solution:
package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
)

// https://github.com/EndlessCheng
func run(in io.Reader, out io.Writer) {
	var n, m, k, w, v, c int
	Fscan(in, &n, &m, &k)
	type pair struct{ w, v int }
	g := make([][]pair, n)
	for i := 0; i < n; i++ {
		Fscan(in, &w, &v, &c)
		g[c-1] = append(g[c-1], pair{w, v})
	}

	f := make([]int, m+1)
	for _, a := range g {
		if a == nil {
			continue
		}
		nf := append(f[:0:0], f...)
		for _, p := range a {
			for j := m; j >= p.w; j-- {
				nf[j] = max(nf[j], max(f[j-p.w]+p.v+k, nf[j-p.w]+p.v))
			}
		}
		f = nf
	}
	Fprint(out, f[m])
}

func main() { run(bufio.NewReader(os.Stdin), os.Stdout) }
func max(a, b int) int { if b > a { return b }; return a }

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Base64;
import java.util.Comparator;
import java.util.StringJoiner;

public class Main {

    static int N, X, K;
    static Product[] P;

    public static void main(String[] args) {
        var sc = new FastScanner(System.in);
        N = sc.nextInt();
        X = sc.nextInt();
        K = sc.nextInt();
        P = new Product[N];
        for (int i = 0; i < N; i++) {
            P[i] = new Product(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        System.out.println(solve());
    }

    static long solve() {
        // まぁナップサックだろう、ただ計算量的にナップサック一回で何とかする必要があるが色...
        // => 色追加する際にだけ色のことは考えるとできそう
        // => 色でsortしておいて色の変わるときにいい感じにする
        Arrays.sort(P, Comparator.comparingInt(p -> p.c));

        // dp[i][j] = i円使って最後に使った色がj(0:古, 1:新)のときの効用
        long[][] dp = new long[X+1][2];
        int c_last = -1;
        for (int n = 0; n < N; n++) {
            var p = P[n];
            if( p.c != c_last ) {
                for (int i = 0; i <= X; i++) {
                    dp[i][0] = Math.max(dp[i][0], dp[i][1]);
                    dp[i][1] = 0;
                }
            }

            for (int i = X; i >= 0; i--) {
                if( i + p.p > X ) continue;

                // 色追加
                dp[i+p.p][1] = Math.max(dp[i+p.p][1], dp[i][0] + p.u + K);

                // 色増えない
                dp[i+p.p][1] = Math.max(dp[i+p.p][1], dp[i][1] + p.u);
            }

            c_last = p.c;
        }


        long ans = 0;
        for (int i = 0; i <= X; i++) {
            ans = Math.max(ans, dp[i][0]);
            ans = Math.max(ans, dp[i][1]);
        }
        return ans;
    }

    static class Product {
        int p, u, c;

        public Product(int p, int u, int c) {
            this.p = p;
            this.u = u;
            this.c = c;
        }
    }

    static void writeLines(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
        pw.flush();
    }

    static void debug(Object... args) {
        var j = new StringJoiner(" ");
        for (var arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j);
    }

    @SuppressWarnings("unused")
    private static class FastScanner {

        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int curbuf;
        private int lenbuf;

        public FastScanner(InputStream in) {
            this.in = in;
            this.curbuf = this.lenbuf = 0;
        }

        public boolean hasNextByte() {
            if (curbuf >= lenbuf) {
                curbuf = 0;
                try {
                    lenbuf = in.read(buffer);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (lenbuf <= 0)
                    return false;
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte())
                return buffer[curbuf++];
            else
                return -1;
        }

        private boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        private void skip() {
            while (hasNextByte() && isSpaceChar(buffer[curbuf]))
                curbuf++;
        }

        public boolean hasNext() {
            skip();
            return hasNextByte();
        }

        public String next() {
            if (!hasNext())
                throw new RuntimeException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (!isSpaceChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            if (!hasNext())
                throw new RuntimeException();
            int c = readByte();
            while (isSpaceChar(c))
                c = readByte();
            boolean minus = false;
            if (c == '-') {
                minus = true;
                c = readByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new RuntimeException();
                res = res * 10 + c - '0';
                c = readByte();
            } while (!isSpaceChar(c));
            return (minus) ? -res : res;
        }

        public long nextLong() {
            if (!hasNext())
                throw new RuntimeException();
            int c = readByte();
            while (isSpaceChar(c))
                c = readByte();
            boolean minus = false;
            if (c == '-') {
                minus = true;
                c = readByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new RuntimeException();
                res = res * 10 + c - '0';
                c = readByte();
            } while (!isSpaceChar(c));
            return (minus) ? -res : res;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public double[] nextDoubleArray(int n) {
            double[] a = new double[n];
            for (int i = 0; i < n; i++)
                a[i] = nextDouble();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        public char[][] nextCharMap(int n, int m) {
            char[][] map = new char[n][m];
            for (int i = 0; i < n; i++)
                map[i] = next().toCharArray();
            return map;
        }
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var [n,x,k] = nexts(3);
  var puc = xArray("[]",n);
  for(var i = 0; i < n; i++){
    var [p,u,c] = nexts(3);
    c--;
    puc[c].push([p,u]);
  }
  var dp1 = xArray(0,x+1);
  var dp2 = xArray(0,x+1);
  for(var i = 0; i < n; i++){
    if(puc[i].length === 0)continue;
    dp2.fill(0);
    for(var j = 0; j < puc[i].length; j++){
      var [p,u] = puc[i][j];
      for(var v = x-p; v >= 0; v--){
        dp2[v+p] = Math.max(dp2[v+p], dp2[v] + u);
      }
      for(var v = x-p; v >= 0; v--){
        dp2[v+p] = Math.max(dp2[v+p], dp1[v] + u);
      }
    }
    for(var v = 0; v < x+1; v++){
      if(dp2[v] === 0)continue;
      dp1[v] = Math.max(dp1[v], dp2[v] + k);
    }
  }

  return dp1[x];
}

Python solution:
n,x,k = map(int,input().split())

T = [[] for i in range(n)]

for i in range(n):
    p,u,c=map(int,input().split())
    c-=1
    
    T[c].append((p,u))
    

DP = [0 for i in range(x+1)]

for i in range(n):
    if len(T[i])==0:
        continue
    
    new = [0 for i in range(x+1)]
    for p, u in T[i]:
        for j in range(x,p-1,-1):
            new[j] = max(new[j],DP[j-p]+u+k, new[j-p]+u)
    
    DP = [max(DP[j],new[j]) for j in range(x+1)]

print(DP[-1])

Ruby solution:
(N,X,K),*PUC = $<.map{|ln| ln.split.map(&:to_i) }
d0 = [0]*(X+1)
PUC.group_by{_3}.each_value{|puc|
	d1 = *d0
	while (p,u = puc.pop)
		(X-p).downto(0){|x|
			d = [d0[x]+K,d1[x]].max+u
			d1[x+p] = d if d1[x+p]<d
		}
	end
	d0 = d1
}
p d0.max