結果

問題 No.3417 Tired Santa
コンテスト
ユーザー tnakao0123
提出日時 2025-12-24 19:48:41
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,563 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 446 ms
コンパイル使用メモリ 45,076 KB
実行使用メモリ 16,612 KB
最終ジャッジ日時 2025-12-24 19:48:43
合計ジャッジ時間 1,755 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:34:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |   scanf("%d%d", &n, &st);
      |   ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:35:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |   for (int i = 0; i < n; i++) scanf("%d", xs + i);
      |                               ~~~~~^~~~~~~~~~~~~~
main.cpp:36:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |   for (int i = 0; i < n; i++) scanf("%d", wis + i);
      |                               ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

/* -*- coding: utf-8 -*-
 *
 * 3417.cc:  No.3417 Tired Santa - yukicoder
 */

#include<cstdio>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 1000;
const long long LINF = 1LL << 62;

/* typedef */

using ll = long long;

/* global variables */

int xs[MAX_N], wis[MAX_N];
ll wss[MAX_N + 1];
ll dp0[MAX_N][MAX_N], dp1[MAX_N][MAX_N];

/* subroutines */

void setmin(ll &a, ll b) { if (a > b) a = b; }

/* main */

int main() {
  int n, st;
  scanf("%d%d", &n, &st);
  for (int i = 0; i < n; i++) scanf("%d", xs + i);
  for (int i = 0; i < n; i++) scanf("%d", wis + i);

  for (int i = 0; i < n; i++) wss[i + 1] = wss[i] + wis[i];

  for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
      dp0[i][j] = dp1[i][j] = LINF;

  int i1 = upper_bound(xs, xs + n, st) - xs;
  int i0 = i1 - 1;
  if (i0 >= 0) dp0[i0][i0] = dp1[i0][i0] = wss[n] * (st - xs[i0]);
  if (i1 < n) dp0[i1][i1] = dp1[i1][i1] = wss[n] * (xs[i1] - st);

  for (int l = 0; l < n - 1; l++)
    for (int i = 0, j = l; j < n; i++, j++) {
      ll w = wss[i] + (wss[n] - wss[j + 1]);
      if (dp0[i][j] < LINF) {
	if (i > 0)
	  setmin(dp0[i - 1][j], dp0[i][j] + w * (xs[i] - xs[i - 1]));
	if (j + 1 < n)
	  setmin(dp1[i][j + 1], dp0[i][j] + w * (xs[j + 1] - xs[i]));
      }
      if (dp1[i][j] < LINF) {
	if (i > 0)
	  setmin(dp0[i - 1][j], dp1[i][j] + w * (xs[j] - xs[i - 1]));
	if (j + 1 < n)
	  setmin(dp1[i][j + 1], dp1[i][j] + w * (xs[j + 1] - xs[j]));
      }
    }

  ll mind = min(dp0[0][n - 1], dp1[0][n - 1]);
  printf("%lld\n", mind);
  
  return 0;
}
0