結果

問題 No.409 ダイエット
ユーザー 0w10w1
提出日時 2019-11-26 11:54:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,772 bytes
コンパイル時間 630 ms
コンパイル使用メモリ 71,384 KB
実行使用メモリ 11,168 KB
最終ジャッジ日時 2024-11-06 15:12:26
合計ジャッジ時間 6,009 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
11,044 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 2 ms
6,820 KB
testcase_13 AC 2 ms
6,820 KB
testcase_14 AC 2 ms
6,816 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 2 ms
6,820 KB
testcase_17 AC 3 ms
6,816 KB
testcase_18 AC 2 ms
6,820 KB
testcase_19 AC 2 ms
6,816 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 2 ms
6,816 KB
testcase_22 AC 2 ms
6,820 KB
testcase_23 AC 2 ms
6,816 KB
testcase_24 AC 2 ms
6,816 KB
testcase_25 AC 2 ms
6,820 KB
testcase_26 AC 2 ms
6,816 KB
testcase_27 AC 2 ms
6,824 KB
testcase_28 AC 2 ms
6,816 KB
testcase_29 AC 2 ms
6,816 KB
testcase_30 AC 2 ms
6,816 KB
testcase_31 AC 2 ms
6,820 KB
testcase_32 AC 2 ms
6,820 KB
testcase_33 AC 2 ms
6,820 KB
testcase_34 AC 2 ms
6,820 KB
testcase_35 AC 3 ms
6,816 KB
testcase_36 AC 3 ms
6,820 KB
testcase_37 AC 3 ms
6,820 KB
testcase_38 AC 3 ms
6,816 KB
testcase_39 AC 3 ms
6,816 KB
testcase_40 AC 3 ms
6,820 KB
testcase_41 AC 4 ms
6,816 KB
testcase_42 AC 3 ms
6,816 KB
testcase_43 AC 3 ms
6,816 KB
testcase_44 AC 2 ms
6,820 KB
testcase_45 AC 3 ms
6,816 KB
testcase_46 AC 3 ms
6,820 KB
testcase_47 AC 3 ms
6,816 KB
testcase_48 AC 3 ms
6,820 KB
testcase_49 AC 3 ms
6,816 KB
testcase_50 AC 3 ms
6,820 KB
testcase_51 AC 3 ms
6,816 KB
testcase_52 AC 3 ms
6,820 KB
testcase_53 AC 3 ms
6,816 KB
testcase_54 AC 3 ms
6,820 KB
testcase_55 AC 31 ms
6,816 KB
testcase_56 TLE -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
testcase_66 -- -
testcase_67 -- -
testcase_68 -- -
testcase_69 -- -
testcase_70 -- -
testcase_71 -- -
testcase_72 -- -
testcase_73 -- -
testcase_74 -- -
testcase_75 -- -
testcase_76 -- -
testcase_77 -- -
testcase_78 -- -
testcase_79 -- -
testcase_80 -- -
testcase_81 -- -
testcase_82 -- -
testcase_83 -- -
testcase_84 -- -
testcase_85 -- -
testcase_86 -- -
testcase_87 -- -
testcase_88 -- -
testcase_89 -- -
testcase_90 -- -
testcase_91 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

class Node {
 public:
  Node(int R, int X) {
    r = R;
    x = X;
  }
  ~Node();
  int r, x;
  Node *pre;
  Node *next;
};

Node::~Node() {}

class List {
 public:
  List(int A, int B) {
    a = A;
    b = B;
    head = NULL;
    tail = NULL;
  }
  ~List();
  void add(Node *n);
  void addToHead(Node *n);
  void prune();
  void print();
  void cut(Node *n);
  void study();
  Node *least();
  List *sleep();
  Node *head;
  Node *tail;
  int a, b;
};

int main() {
  int N, A, B, W;
  int s, x;
  cin >> N >> A >> B >> W;
  int *D = new int[N];
  List *list = new List(A, B);
  for (int i = 0; i < N; i++) {
    cin >> D[i];
  }

  Node *n = new Node(W, 0);
  list->add(n);

  for (int i = 0; i < N; i++) {
    n = list->least();
    Node *sleepNode = new Node(n->r + D[i], 0);
    list->study();
    list->addToHead(sleepNode);
    list->prune();
    // list->print();
  }

  n = list->least();

  cout << n->r << endl;

  delete list;
}

List::~List() {
  Node *cur = head;
  if (cur) {
    while (cur->next) {
      head = cur->next;
      delete cur;
      cur = head;
    }
  }
  if (cur) delete cur;
}
// add the node n to the tail of the list
void List::add(Node *n) {
  if (!head) {
    n->pre = NULL;
    n->next = NULL;
    head = n;
    tail = n;
  } else {
    n->pre = tail;
    n->next = NULL;
    tail->next = n;
    tail = n;
  }
}
// add the node n to the head of the list
void List::addToHead(Node *n) {
  if (!head) tail = n;
  n->next = head;
  head = n;
}
// prune the decision tree
void List::prune() {
  Node *n1, *n2;
  n1 = head;
  if (!n1) return;
  n2 = head->next;
  while (n1->next) {
    while (n2) {
      if (n2->r > n1->r) {
        n1->next = n2->next;
        if (n2 == tail) tail = n1;
      } else
        break;
      delete n2;
      n2 = n1->next;
    }
    if (!n2) {
      n1->next = NULL;
      tail = n1;
    } else {
      n1 = n2;
      n2 = n2->next;
    }
  }
}
// print the content of the nodes in the list
void List::print() {
  Node *cur = head;
  while (cur) {
    cout << cur->r << " " << cur->x << endl;
    cur = cur->next;
  }
}
// let n to be the tail node
void List::cut(Node *n) {
  Node *cur = n->next;
  Node *tmp;
  while (cur) {
    tmp = cur;
    cur = cur->next;
    delete tmp;
  }
  n->next = NULL;
  tail = n;
}
// let every nodes in the list study next day
void List::study() {
  Node *cur = head;
  while (cur) {
    cur->x = cur->x + 1;
    cur->r = cur->r + cur->x * b - a;
    cur = cur->next;
  }
}
// return the node with min r
Node *List::least() {
  Node *cur = head;
  Node *leastNode = head;
  int min = head->r;
  while (cur) {
    if (cur->r < min) {
      leastNode = cur;
      min = cur->r;
    }
    cur = cur->next;
  }
  return leastNode;
}
0