結果

問題 No.409 ダイエット
ユーザー 0w1
提出日時 2019-11-26 11:54:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,772 bytes
コンパイル時間 642 ms
コンパイル使用メモリ 68,912 KB
最終ジャッジ日時 2025-01-08 05:38:37
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 71 WA * 20 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

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