public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int steps = Integer.parseInt(scanner.nextLine());int[] nums = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int k = Integer.parseInt(scanner.nextLine());calculateMaxScoreSum(steps, nums, k);}public static int calculateMaxScoreSum(int steps, int[] nums, int k) {int[] dp = new int[steps];dp[0] = nums[0];for (int i = 1; i < dp.length; i++) {int max = Integer.MIN_VALUE;for (int j = 1; j <= k; j++) {if (i - j >= 0)max = Math.max(max, nums[i - j]);}dp[i] = nums[i] + max;}return dp[steps - 1];}

public static void main(String[] args) {Scanner in = new Scanner(System.in);int[] map = Arrays.stream(in.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int num = Integer.parseInt(in.nextLine());List list = Arrays.stream(map).boxed().collect(Collectors.toList());int initNum = Integer.parseInt(in.nextLine());getResult(list, initNum);}public static void getResult(List<Integer> list, int initNum) {int count = 1;int index = 0;while (!list.isEmpty()) {if (index >= list.size()) {index = 0;continue;}if (count == initNum) {if (list.size() == 1) {System.out.print(list.get(index));} elseSystem.out.print(list.get(index) + ",");initNum = list.get(index);list.remove(index);count = 1;continue;}index++;count++;}System.out.println();}

列方程 double L= (num * 2 + i - i * i) / 4.0;如果 L 是整数就存在public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = in.nextInt();System.out.println(getReslut(num));}public static int getReslut(int num) {int count = 1;for (int i = 1; i <= num / i; i++) {double temp = (num * 2 + i - i * i) / 4.0;if (temp == (int)temp)count++;}return count;}

static char[] map = new char[35];public static void main(String[] args) {for (int i = 0; i < map.length; i++) {if (i < 10)map[i] = (char) ('0' + i);elsemap[i] = (char) ('a' + i - 10);}Scanner inputScanner = new Scanner(System.in);int base = inputScanner.nextInt();String num1 = inputScanner.next(); // 被减数String num2 = inputScanner.next(); // 减数StringBuilder num1Builder = new StringBuilder(num1);StringBuilder num2Builder = new StringBuilder(num2);if (num1Builder.length() > num2Builder.length()) {System.out.print(0 + " ");System.out.print(getResult(num1Builder, num2Builder, base));} else if (num1Builder.length() < num2Builder.length()) {System.out.print(1 + " ");System.out.println(getResult(num2Builder, num1Builder, base));} else {for (int i = 0; i < num1Builder.length(); i++) {if (num1Builder.charAt(i) > num2Builder.charAt(i)) {System.out.print(0 + " ");System.out.print(getResult(num1Builder, num2Builder, base));break;} else if (num1Builder.charAt(i) < num2Builder.charAt(i)){System.out.print(1 + " ");System.out.println(getResult(num2Builder, num1Builder, base));break;}if (num1Builder.length() - 1 == i) {System.out.print(0 + " ");System.out.print(0);}}}}public static String getResult(StringBuilder num1Builder, StringBuilder num2Builder, int base) {StringBuilder ans = new StringBuilder();num1Builder.reverse();num2Builder.reverse();for (int i = 0; i < num1Builder.length(); i++) {if (i >= num2Builder.length()) {ans.append(num1Builder.substring(i, num1Builder.length()));break;}char num1 = num1Builder.charAt(i);char num2 = num2Builder.charAt(i);if (num1 >= num2)ans.append(map[num1 - num2]);else {backtrack(num1Builder, 1 , i, base);ans.append(map[num1 + base - num2]);}}return ans.reverse().toString();}public static void backtrack(StringBuilder num1Builder, int index, int i, int base) {if (num1Builder.charAt(i + index) != '0') {char ch = num1Builder.charAt(i + index);num1Builder.delete(i + index, i + index + 1);num1Builder.insert(i + index, (char)(ch - 1));} else {backtrack(num1Builder, index + 1 , i, base);num1Builder.delete(i + index, i + index + 1);num1Builder.insert(i + index, (char)(base - 1));}}

并查集+Kruskal 算法 解决public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = Integer.parseInt(in.nextLine());int n = Integer.parseInt(in.nextLine());Map[] maps = new Map[n];for (int i = 0; i < n; i++) {int[] map =  Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();maps[i] = new Map(map[0], map[1], map[2], map[3] == 1);}Arrays.sort(maps, new Comparator<Map>() {@Overridepublic int compare(Map o1, Map o2) {if (o1.has)return -1;if (o2.has)return 1;return o1.cost - o2.cost;}});UnionFindSet unionFindSet = new UnionFindSet(num);int cost = 0;for (int i = 0; i < maps.length; i++) {if (maps[i].has) {unionFindSet.union(maps[i].x - 1, maps[i].y - 1);continue;}if (unionFindSet.find(maps[i].x - 1) != unionFindSet.find(maps[i].y - 1)) {unionFindSet.union(maps[i].x - 1, maps[i].y - 1);cost += maps[i].cost;}}System.out.println(cost);}static class Map {public int x;public int y;public int cost;public boolean has = false;public Map(int x, int y, int cost, boolean has) {this.x = x;this.y = y;this.cost = cost;this.has = has;}}static class UnionFindSet {int[] parent = null;public UnionFindSet(int count) {this.parent = new int[count];for (int i = 0; i < parent.length; i++) {parent[i] = i;}}public int find(int x) {if (parent[x] == x)return x;else return parent[x] = find(parent[x]);}public void union(int i , int j) {int f_i = find(i);int f_j = find(j);if (f_i != f_j) {for (int k = 0; k < parent.length; k++) {if (parent[k] == f_j)parent[k] = f_i;}}}}

public static void main(String[] args) {Scanner in = new Scanner(System.in);int num = Integer.parseInt(in.nextLine());String str = in.nextLine();int[] assets = Arrays.stream(str.split(" ")).mapToInt(Integer::parseInt).toArray();int[][] map = new int[num - 1][2];for (int i = 0; i < num - 1; i++) {map[i] = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();}Node head = buildTree(map, assets);//        printTree(head);System.out.println(getMaxFamlie(head));}public static int getMaxFamlie(Node head) {if (head == null)return 0;int max = 0;max += head.value;if (head.left != null)max += head.left.value;if (head.right != null)max += head.right.value;max = Math.max(getMaxFamlie(head.left), max);max = Math.max(getMaxFamlie(head.right), max);return max;}public static Node buildTree(int[][] map, int[] assets) {int count = 0;Node[] nodes = new Node[assets.length];for (int i = 0; i < assets.length; i++) {nodes[i] = new Node(assets[i]);}for (int i = 0; i < map.length; i++) {if (nodes[map[i][0] - 1].left == null)nodes[map[i][0] - 1].left = nodes[map[i][1] - 1];else nodes[map[i][0] - 1].right = nodes[map[i][1] - 1];}return nodes[0];}public static void printTree(Node head) {if (head == null)return;System.out.println(head.value);printTree(head.left);printTree(head.right);}static class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}}

public static void main(String[] args) {Scanner in = new Scanner(System.in);String word = in.nextLine();System.out.println(getResult(word));}public static int getResult(String word) {Stack<Character> stacks = new Stack<>();int max = 0;boolean isInvalid = false;for (int i = 0; i < word.length(); i++) {switch (word.charAt(i)) {case '(' : {stacks.add('(');max = Math.max(max, stacks.size());} break;case '[' : {stacks.add('[');max = Math.max(max, stacks.size());} break;case '{' : {stacks.add('{');max = Math.max(max, stacks.size());} break;case ')' : {if (stacks.pop() != '(')isInvalid = true;break;}case ']' : {if (stacks.pop() != '[')isInvalid = true;break;}case '}' : {if (stacks.pop() != '{')isInvalid = true;break;}default:break;}}if (isInvalid) return 0;return max;}

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] matrix = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {matrix[i][j] = sc.nextInt();}}getResult(matrix);}public static int getResult(int[][] map) {int max = Integer.MIN_VALUE;for (int i = 0; i < map.length; i++) {max = Math.max(getSubMax(map[i]), max);for (int j = 1; j < map.length; j++) {max = Math.max(max, getSubMax(getMatixMax(map, i, j)));}}return max;}public static int getSubMax(int[] sub) {int res = sub[0];int max = sub[0];for (int i = 1; i < sub.length; i++) {max = Math.max(sub[i] + max, sub[i]);res = Math.max(res, max);}return res;}public static int[] getMatixMax(int[][] map, int begin, int end) {int line = map[begin].length;int[] zip = new int[line];for (int i = 0; i < line; i++) {for (int j = begin; j <= end; j++) {zip[i] += map[j][i];}}return zip;}

public static void main(String[] args) {Scanner in = new Scanner(System.in);String[] prices = in.nextLine().split(" ");int[] pricesTemp = changeToRMB(prices);System.out.println(getResult(pricesTemp));}public static int getResult(int[] prices) {int sum = 0;int price = 0;for (int i = 0; i < prices.length; i++) {if (isPeak(prices, i) && price != 0)sum += prices[i] - price;if (isValley(prices, i))price = prices[i];}return sum;}public static int[] changeToRMB(String[] prices) {int[] pricesTemp = new int[prices.length];for (int i = 0; i < prices.length; i++) {if (prices[i].endsWith("Y"))pricesTemp[i] = Integer.parseInt(prices[i].substring(0, prices[i].length() - 1));elsepricesTemp[i] = Integer.parseInt(prices[i].substring(0, prices[i].length() - 1)) * 7;}return pricesTemp;}public static boolean isPeak(int[] prices, int i) {if (i == 0 && prices[i + 1] < prices[i])return true;else if (i == 0)return false;if (i == prices.length - 1 && prices[i - 1] < prices[i])return true;else if (i == prices.length - 1)return false;if (prices[i - 1] < prices[i] && prices[i + 1] < prices[i])return true;return false;}public static boolean isValley(int[] prices, int i) {if (i == 0 && prices[i + 1] > prices[i])return true;else if (i == 0)return false;if (i == prices.length - 1 && prices[i - 1] > prices[i])return true;else if (i == prices.length - 1)return false;if (prices[i - 1] > prices[i] && prices[i + 1] > prices[i])return true;return false;}

public static void main(String[] args) {Scanner in = new Scanner(System.in);int maxCount = Integer.parseInt(in.nextLine());String word = in.nextLine();System.out.println(getResult(word, maxCount));}public static String getResult(String word, int maxCount) {StringBuilder wordBuilder = new StringBuilder(word);int i = 0;int index = 0;int left = 0, right = 0;StringBuilder ans = new StringBuilder();while (i < wordBuilder.length()) {if (wordBuilder.charAt(i) == '-') {index++;wordBuilder.delete(i, i + 1);}if (index == 1) {ans.append(wordBuilder.substring(0, i) + "-");left = i;right++;i++;index++;continue;} else if (index > 0 && right - left == maxCount){String temp = wordBuilder.substring(left, right);change(temp);ans.append(temp + "-");left = i;}if (i == wordBuilder.length() - 1) {String temp = wordBuilder.substring(left, wordBuilder.length());change(temp);ans.append(temp + "-");}right++;i++;}return ans.delete(ans.length()-1, ans.length()).toString();}public static void change(String word) {int low = 0;int uppper = 0;for (int i = 0; i < word.length(); i++) {if (word.charAt(i) >= 'a' && word.charAt(i) <= 'z')low++;else if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z')uppper++;}if (low > uppper)word.toLowerCase();if (uppper > low)word.toUpperCase();}

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] price = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] newPrice = getLastPrice(price);for (int i = 0; i < newPrice.length; i++) {System.out.print(newPrice[i] + " ");}}public static int[] getLastPrice(int[] price) {int[] newPrice = new int[price.length];for (int i = 0; i < price.length; i++) {if (i + 1 < price.length && price[i + 1] < price[i])newPrice[i] = price[i] + price[i + 1];elsenewPrice[i] = price[i];}if (newPrice[price.length - 1] > price[0])newPrice[price.length - 1] += price[0];return newPrice;}

public static void main(String[] args) {Scanner in = new Scanner(System.in);int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int studentCount = nums[0];int subjectCount = nums[1];String[][] map = new String[studentCount + 1][subjectCount + 1];for (int i = 0; i < studentCount + 1; i++) {if (i == 0) {String[] subjects = in.nextLine().split(" ");for (int j = 0; j < subjectCount; j++) {map[i][j + 1] = subjects[j];}} else {String[] student = in.nextLine().split(" ");for (int j = 0; j < student.length; j++) {map[i][j] = student[j];}}}String sub = in.nextLine();String[][] map1 = getRanks(sub, map);for (int i = 0; i < map1.length; i++) {System.out.print(map1[i][0] + " ");}}public static String[][] getRanks(String subjects, String[][] map) {int sub = -1;for (int i = 1; i < map[0].length; i++) {if (map[0][i].equals(subjects))sub = i;}int finalSub = sub;String[][] map1 = new String[map.length - 1][map[0].length];for (int i = 1; i < map.length; i++) {map1[i - 1] = map[i];}Arrays.sort(map1, new Comparator<String[]>() {@Overridepublic int compare(String[] o1, String[] o2) {if (finalSub != -1)return Integer.parseInt(o2[finalSub]) - Integer.parseInt(o1[finalSub]);else {int o1Sum = 0;int o2Sum = 0;for (int i = 1; i < o1.length; i++) {o1Sum += Integer.parseInt(o1[i]);o2Sum += Integer.parseInt(o2[i]);}return o1Sum - o2Sum;}}});return map1;}

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int GPU = scanner.nextInt();int runableCount = scanner.nextInt();PriorityQueue priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});for (int i = 0; i < runableCount; i++) {priorityQueue.add(scanner.nextInt());}System.out.println(getMinTime(GPU, priorityQueue));}public static int getMinTime(int GPUCount, PriorityQueue<Integer> runables) {GPUPoll poll = new GPUPoll(GPUCount);int i = 0;while (!runables.isEmpty()) {while (poll.hasBanancePoll() != -1) {if (runables.peek() != null)poll.poll[poll.hasBanancePoll()] = runables.poll();else break;}poll.execut();i++;}i += poll.getMaxTime();return i;}static class GPUPoll {int[] poll;public GPUPoll(int count) {this.poll = new int[count];}public void execut() {for (int i = 0; i < poll.length; i++) {poll[i] -= 1;}}public int hasBanancePoll() {for (int i = 0; i < poll.length; i++) {if (poll[i] == 0)return i;}return -1;}public int getMaxTime() {int max = Integer.MIN_VALUE;for (int i = 0; i < poll.length; i++) {if (poll[i] > 0) {max = Math.max(max,poll[i]);}}return max;}}

public static void main(String[] args) {Scanner in = new Scanner(System.in);int count = in.nextInt();int time = in.nextInt();LinkedList<int[]> runables = new LinkedList<>();for (int i = 0; i < count; i++) {int[] runable = new int[2];runable[0] = in.nextInt();runable[1] = in.nextInt();runables.add(runable);}System.out.println(getMaxScore(runables, time));}public static int getMaxScore(LinkedList<int[]> runables, int time) {Collections.sort(runables, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0] == o2[0])return o2[1] - o1[1];return o1[0] - o2[0];}});int score = 0;for (int i = 1; i < time; i++) {int[] runable = runables.pollFirst();if (runable[0] >= i) {score += runable[1];while (runables.peekFirst() != null && runables.peekFirst()[0] == runable[0]) {runables.pollFirst();}}}return score;}