986

class Solution {
if (head == null) return null;
HashMap<ListNode, ListNode> pos = new HashMap<ListNode, ListNode>();
pos.put(null,null);
for(ListNode p = head; p != null; p = p.next){
pos.put(p, new ListNode(p.val));
}
for (ListNode p = head; p != null; p = p.next){
pos.get(p).next = pos.get(p.next);
pos.get(p).random = pos.get(p.random);
}
}
}


import java.io.*;

public class Main {
public static void main(String[] args) throws IOException {
int[] h = new int[n];
for (int i = 0; i < n; i++) {
h[i] = Integer.parseInt(temp[i]);
}
int l = 0, r = 100000;
while(l < r){
int mid = (l + r) >> 1;
int e = mid;
for (int i = 0; i < n && e >= 0 && e <= 100000; i++) {
e = 2*e - h[i];
}
if (e < 0) l = mid + 1;
else r = mid;
}
System.out.println(l);
}
}


import java.io.*;

public class Main{
public static void main(String[] args) throws IOException {
int n = Integer.parseInt(temp[0]), m = Integer.parseInt(temp[1]);
int[][] f = new int[n+1][m+1];
int res = 0;
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
f[i][j] = Integer.parseInt(temp[j-1]);
if (f[i][j] == 1){
f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
res = Math.max(res, f[i][j]);
}
}
}
System.out.println(res*res);
}
}


import java.io.*;
import java.util.ArrayDeque;

public class Main{
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
ArrayDeque<Integer> nums = new ArrayDeque<>();
ArrayDeque<Character> ops = new ArrayDeque<>();
for (int i = 0; i < temp.length; i++) {
char c = temp[i];
//当是数字时，计算数字的值
if (c >= '0' && c <= '9'){
int j = i+1, value = Integer.parseInt(String.valueOf(c));
while(j < temp.length && temp[j] >= '0' && temp[j] <= '9'){
value = (value*10 + Integer.parseInt(String.valueOf(temp[j])))% 10000;
j++;
}
nums.push(value);
i = j-1;
//当是加号时，只要操作符栈非空，就一直计算
}else if (c == '+'){
while(!ops.isEmpty()){
char d = ops.pop();
if (d == '+'){
nums.push((nums.pop() + nums.pop())% 10000);
}else{
nums.push((nums.pop() * nums.pop())% 10000);
}
}
ops.push(c);
//当是乘号时，仅当操作符栈非空且为乘号时才进行计算
}else{
while(!ops.isEmpty() && ops.peek() == '*'){
nums.push((nums.pop() * nums.pop())% 10000);
ops.pop();
}
ops.push(c);
}
}
//当操作符栈非空时，按顺序计算数值即可，只会存在最多一个乘号
while(!ops.isEmpty()){
char x = ops.pop();
if (x == '+'){
nums.push((nums.pop() + nums.pop())% 10000);
}else{
nums.push((nums.pop() * nums.pop())% 10000);
}
}
System.out.println(nums.pop() % 10000);
}
}


import java.io.*;

public class Main{
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int[] h = new int[n+1];
for (int i = 0; i < n; i++) {
h[i] = Integer.parseInt(temp[i]);
}
int res = 0;
for(int i = 0, j = n-1; i < j; ) {
res = Math.max(res, Math.min(h[i], h[j]) * (j-i));
if (h[i] < h[j]) i++;
else j--;
}
System.out.println(res);
}
}


import java.io.*;
import java.util.ArrayDeque;

public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
ArrayDeque<Integer> q = new ArrayDeque<>(10000+10);
int[] h = new int[m+2];
int res = 0;
for (int i = 0; i < m; i++) {
h[i] = Integer.parseInt(temp[i]);
}
for (int i = 0; i < m; i++) {
int last = 0;//用于存放上一个较小的高度值是多少
while(!q.isEmpty() && h[q.peek()] <= h[i]){
//当队列非空且队头元素小于当前元素时，计算两者之间的面积
res += (h[q.peek()] - last) * (i - q.peek() - 1);
//更新高度值
last = h[q.peek()];
q.pop();
}
if (!q.isEmpty()){
res += (h[i] - last) * (i - q.peek() - 1);
}
q.push(i);
}
System.out.println(res);
}
}


import java.io.*;
import java.util.ArrayDeque;

public class Main {
static ArrayDeque<Integer> queue = new ArrayDeque<>(1002);
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(temp[0]);
int m = Integer.parseInt(temp[1]);
int[][] s = new int[n+2][m+2];
int[] l = new int[m+2], r = new int[m+2];
//将左右两侧边界初始化为-1,
for (int i = 0; i <= n; i++) {
s[i][0] = s[i][m+1] = -1;
}
//读入数据
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = temp[j-1].equals("R") ? 0 : s[i-1][j] + 1;
}
}
long res = 0;
for (int i = 1; i <= n; i++) {
res =Math.max(res, work(s[i], l, r, m));
}
writer.write(res*3+"");
writer.flush();
}
static long work(int[] h,int[] l,int[] r, int m){
queue.clear();
queue.push(0);
for (int i = 1; i <= m; i++) {
while(h[i] <= h[queue.peek()]) queue.pop();
l[i] = queue.peek();
queue.push(i);
}
queue.clear();
queue.push(m+1);
for (int i = m; i > 0; i--) {
while(h[i] <= h[queue.peek()]) queue.pop();
r[i] = queue.peek();
queue.push(i);
}
long res = 0;
for (int i = 1; i <= m; i++) {
res = Math.max(res, (long)h[i]*(r[i]-l[i]-1));
}
return res;
}
}


import java.io.*;
import java.util.ArrayDeque;

public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
//都多申请几位，方便处理边界
ArrayDeque<Integer> queue = new ArrayDeque<>(100000 + 10);
int[] h = new int[100000 +2];
int[] l = new int[100000 +2];
int[] r = new int[100000 +2];
h[0] = -1;//将左边界初始化为-1，方便进行边界判断
while(Integer.parseInt(temp[0]) != 0){
int n = Integer.parseInt(temp[0]);
h[n+1] = -1;//同上
for (int i = 1; i <= n; i++) {
h[i] = Integer.parseInt(temp[i]);
}
//计算出左侧第一个比当前数小的数据的位置
queue.push(0);
for (int i = 1; i <= n; i++) {
while(h[i] <= h[queue.peek()]){
queue.pop();
}
l[i] = queue.peek();
queue.push(i);
}
queue.clear();
//计算出右侧第一个比当前数小的数据的位置
queue.push(n+1);
for (int i = n; i > 0; i--) {
while(h[i] <= h[queue.peek()]){
queue.pop();
}
r[i] = queue.peek();
queue.push(i);
}
long res = 0;
for (int i = 1; i <= n; i++) {
//这里在计算时一定要手动强转为long，不然会按照int计算
res = Math.max(res, (long)h[i]*(r[i] - l[i] - 1));
}
writer.write(res+"\n");
}
writer.flush();
}
}


import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(temp[0]);
int k = Integer.parseInt(temp[1]);
int[] w = new int[n+1];
for (int i = 0; i < n; i++) {
w[i+1] = Integer.parseInt(temp[i]);
}
int[][][] f = new int[2][100010][110];
//我为了方便初始化数据，改了一下状态数组的定义顺序
for (int i = 0; i < n + 1; i++) {
Arrays.fill(f[0][i], -0x3f3f3f3f);
Arrays.fill(f[1][i], -0x3f3f3f3f);
}
f[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
f[0][i][j] = f[0][i-1][j];
if (j > 0){
f[0][i][j] = Math.max(f[0][i][j], f[1][i-1][j-1]+w[i]);
}
f[1][i][j] = Math.max(f[1][i-1][j], f[0][i-1][j]-w[i]);
}
}
int res = 0;
for (int i = 0; i <= k; i++) {
res = Math.max(res, f[0][n][i]);
}
System.out.println(res);
}
}



import java.io.*;
import java.util.*;

public class Main{
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
ArrayList<Pair> list = new ArrayList<>(10000);
PriorityQueue<Pair> res = new PriorityQueue<>((o1, o2) -> o1.value-o2.value);
while(sc.hasNext()){
int n = sc.nextInt();
list.clear();
res.clear();
for (int i = 0; i < n; i++) {
int value = sc.nextInt();
int day = sc.nextInt();
}
Collections.sort(list,(o1, o2) -> o1.day-o2.day);
int days = 0;
int le = 0, re = list.size();
while(le<re){
Pair p = list.get(le++);
days = p.day;
if (res.size() > days){
res.poll();
}
}
int out = 0;
while(!res.isEmpty()){
out += res.poll().value;
}
writer.write(out+"\n");
}
writer.flush();
}
static class Pair{
int day;
int value;

public Pair(int day, int value) {
this.day = day;
this.value = value;
}
}
}