結果
| 問題 | No.45 回転寿司 |
| ユーザー |
 aimBULL
|
| 提出日時 | 2016-06-04 18:20:41 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,607 bytes |
| コンパイル時間 | 2,671 ms |
| コンパイル使用メモリ | 87,880 KB |
| 実行使用メモリ | 56,916 KB |
| 最終ジャッジ日時 | 2024-05-03 15:24:58 |
| 合計ジャッジ時間 | 14,867 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
ソースコード
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] sushi = new int[n];
for(int i = 0; i < n && sc.hasNextInt(); i++){
sushi[i] = sc.nextInt();
}
sc.close();
int[] memo = Main.calc(n, sushi);
Arrays.sort(memo);
System.out.println(memo[memo.length - 1]);
}
// データの格納領域を作成する
public static int[] create(int n){
int[] memo = new int[(n + 1) / 2 + 1];
memo[0] = 0;
for(int i = 1; i < memo.length; i++){
memo[i] = Integer.MIN_VALUE;
}
return memo;
}
// 最大の美味しさを計算する
public static int[] calc(final int n, final int[] sushi){
Deque<Node> stack = new ArrayDeque<>();
int[] memo = create(n);
// 1つ目の寿司を選んだ状態を処理スタックに追加
for(int i = 0; i < sushi.length; i++){
Node startNode = new Node(i, i, 1, sushi[i]);
stack.push(startNode);
}
// 寿司１つの場合の最大美味しさは事前に計算する
int[] tmp = sushi.clone();
Arrays.sort(tmp);
memo[1] = tmp[tmp.length - 1];
while(stack.size() > 0){
Node current = stack.peek();
// 存在しない寿司は削除して次へ
if(current.pos >= sushi.length){
stack.pop();
continue;
}
// 存在しない寿司を取る場合は削除して次へ
final int pos = current.nextPos;
if(pos >= sushi.length){
stack.pop();
continue;
}
// 最大の美味しさを更新
final int umami = current.totalUmami + sushi[pos];
final int dishes = current.dishes + 1;
if(umami >= memo[dishes]){
memo[dishes] = umami;
}
// 次の寿司を選んだ状態を追加する
stack.push(new Node(current.id, pos, dishes, umami));
// 今回とは別の寿司を選ぶため更新をかける
current.nextPos++;
}
return memo;
}
}
class Sushi{
int umami;
int pos;
public Sushi(int pos, int umami) {
this.pos = pos;
this.umami = umami;
}
}
class Node extends Sushi{
@Deprecated
int id;
@Deprecated
int dishes;
int nextPos;
int totalUmami;
public Node(int id, int pos, int dishes, int totalUmami) {
super(pos, -1);
this.id = id;
// 次にとることができる寿司は2つ以上離れている
nextPos = pos + 2;
this.dishes = dishes;
this.totalUmami = totalUmami;
}
@Override
public String toString() {
return "{id=" + id + " dishes=" + dishes + " pos=" + pos + " nextpos=" + nextPos + " totalUmami=" + totalUmami + "}";
}
}