結果

問題 No.738 平らな農地
ユーザー tnakao0123tnakao0123
提出日時 2018-09-29 22:11:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 95 ms / 2,000 ms
コード長 4,917 bytes
コンパイル時間 951 ms
コンパイル使用メモリ 94,112 KB
実行使用メモリ 8,844 KB
最終ジャッジ日時 2024-10-12 08:45:03
合計ジャッジ時間 6,918 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 3 ms
6,816 KB
testcase_06 AC 3 ms
6,816 KB
testcase_07 AC 4 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,824 KB
testcase_10 AC 2 ms
6,820 KB
testcase_11 AC 2 ms
6,824 KB
testcase_12 AC 2 ms
6,816 KB
testcase_13 AC 3 ms
6,816 KB
testcase_14 AC 2 ms
6,820 KB
testcase_15 AC 78 ms
8,472 KB
testcase_16 AC 84 ms
8,296 KB
testcase_17 AC 74 ms
8,368 KB
testcase_18 AC 80 ms
8,156 KB
testcase_19 AC 55 ms
8,680 KB
testcase_20 AC 83 ms
8,332 KB
testcase_21 AC 78 ms
8,684 KB
testcase_22 AC 81 ms
8,476 KB
testcase_23 AC 74 ms
8,392 KB
testcase_24 AC 66 ms
8,512 KB
testcase_25 AC 3 ms
6,820 KB
testcase_26 AC 2 ms
6,820 KB
testcase_27 AC 2 ms
6,816 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,816 KB
testcase_32 AC 2 ms
6,816 KB
testcase_33 AC 2 ms
6,820 KB
testcase_34 AC 2 ms
6,816 KB
testcase_35 AC 2 ms
6,816 KB
testcase_36 AC 2 ms
6,820 KB
testcase_37 AC 2 ms
6,820 KB
testcase_38 AC 2 ms
6,816 KB
testcase_39 AC 2 ms
6,816 KB
testcase_40 AC 2 ms
6,816 KB
testcase_41 AC 2 ms
6,816 KB
testcase_42 AC 2 ms
6,816 KB
testcase_43 AC 2 ms
6,816 KB
testcase_44 AC 2 ms
6,816 KB
testcase_45 AC 86 ms
8,684 KB
testcase_46 AC 83 ms
8,272 KB
testcase_47 AC 83 ms
8,628 KB
testcase_48 AC 81 ms
8,348 KB
testcase_49 AC 77 ms
8,568 KB
testcase_50 AC 84 ms
8,656 KB
testcase_51 AC 89 ms
8,608 KB
testcase_52 AC 84 ms
8,232 KB
testcase_53 AC 86 ms
8,460 KB
testcase_54 AC 86 ms
8,720 KB
testcase_55 AC 86 ms
8,544 KB
testcase_56 AC 85 ms
8,728 KB
testcase_57 AC 81 ms
8,136 KB
testcase_58 AC 85 ms
8,484 KB
testcase_59 AC 84 ms
8,660 KB
testcase_60 AC 84 ms
8,724 KB
testcase_61 AC 84 ms
8,616 KB
testcase_62 AC 82 ms
8,276 KB
testcase_63 AC 95 ms
8,628 KB
testcase_64 AC 91 ms
8,632 KB
testcase_65 AC 13 ms
6,816 KB
testcase_66 AC 13 ms
6,820 KB
testcase_67 AC 38 ms
8,180 KB
testcase_68 AC 38 ms
8,416 KB
testcase_69 AC 43 ms
8,576 KB
testcase_70 AC 43 ms
8,612 KB
testcase_71 AC 41 ms
8,644 KB
testcase_72 AC 50 ms
8,144 KB
testcase_73 AC 53 ms
8,512 KB
testcase_74 AC 47 ms
8,608 KB
testcase_75 AC 41 ms
8,156 KB
testcase_76 AC 42 ms
8,316 KB
testcase_77 AC 40 ms
8,328 KB
testcase_78 AC 43 ms
8,684 KB
testcase_79 AC 53 ms
8,760 KB
testcase_80 AC 49 ms
8,468 KB
testcase_81 AC 48 ms
8,428 KB
testcase_82 AC 49 ms
8,484 KB
testcase_83 AC 63 ms
8,820 KB
testcase_84 AC 63 ms
8,844 KB
testcase_85 AC 21 ms
8,716 KB
testcase_86 AC 24 ms
8,376 KB
testcase_87 AC 64 ms
8,484 KB
testcase_88 AC 58 ms
8,208 KB
testcase_89 AC 1 ms
6,816 KB
testcase_90 AC 1 ms
6,820 KB
testcase_91 AC 1 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:216:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  216 |   scanf("%d%d", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:217:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  217 |   for (int i = 0; i < n; i++) scanf("%d", &as[i]);
      |                               ~~~~~^~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 738.cc:  No.738 平らな農地 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 100000;
const long long LINF = 1LL << 60;

/* typedef */

typedef long long ll;
typedef pair<ll,ll> pll;

template <typename T, const int BUFSIZE>
struct TreapSum {
  struct Node {
    T key, minkey, sum;
    int fix, size;
    Node *left, *right;

    void print(int k) {
      printf("%d: key=%lld, minkey=%lld, sum=%lld, fix=%d, size=%d\n",
	     k, (ll)key, (ll)minkey, (ll)sum, fix, size);
    }
    void print() { print(0); }
  };
  typedef Node *node;
  typedef pair<T,T> ptt;

  node root, nullnode, buf;
  Node buf0[BUFSIZE], buf1;

  const T TINF;
  
  TreapSum(T _TINF): TINF(_TINF) {
    nullnode = &buf1;
    nullnode->left = nullnode->right = nullnode;
    nullnode->key = nullnode->minkey = TINF;
    nullnode->sum = 0;
    nullnode->fix = nullnode->size = 0;
    clear();
    srand(time(NULL));
  }

  void clear() { buf = buf0; root = nullnode; }
  int size() { return root->size; }
  T sum() { return root->sum; }

  void update(node& t) {
    t->size = 1 + t->left->size + t->right->size;
    t->minkey = t->key;
    if (t->minkey > t->left->minkey) t->minkey = t->left->minkey;
    if (t->minkey > t->right->minkey) t->minkey = t->right->minkey;
    t->sum = t->key + t->left->sum + t->right->sum;
  }

  node gen_node(T x) {
    node t = buf++;
    t->left = t->right = nullnode;
    t->key = t->minkey = t->sum = x;
    t->fix = rand();
    t->size = 1;
    return t;
  }
  
  void rot_l(node& k1) {
    node k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void rot_r(node& k1) {
    node k2 = k1->left;
    k1->left = k2->right;
    k2->right = k1;
    update(k1);
    update(k2);
    k1 = k2;
  }

  void insert(node& t, T x) {
    if (t == nullnode)
      t = gen_node(x);
    else {
      //if (t->key == x) return;
      if (x < t->key) {
	insert(t->left, x);
	update(t);
	if (t->left->fix > t->fix) rot_r(t);
      }
      else {
	insert(t->right, x);
	update(t);
	if (t->right->fix > t->fix) rot_l(t);
      }
    }
  }
  void insert(T x) { insert(root, x); }

  void remove_node(node& t) {
    if (t == nullnode) return;
    if (t->left == nullnode || t->right == nullnode) {
      if (t->left == nullnode)
	t = t->right;
      else
	t = t->left;
    }
    else {
      if (t->left->fix < t->right->fix) {
	rot_l(t);
	remove_node(t->left);
	update(t);
      }
      else {
	rot_r(t);
	remove_node(t->right);
	update(t);
      }
    }
  }

  void remove(node& t, T x) {
    if (t != nullnode) {
      if (t->key == x)
	remove_node(t);
      else if (x < t->key) {
	remove(t->left, x);
	update(t);
      }
      else {
	remove(t->right, x);
	update(t);
      }
    }
  }
  void remove(T x) { remove(root, x); }
  
  ptt findat(int i) {
    node t = root;
    T lsum = 0;
    while (t != nullnode) {
      int lsize = t->left->size;
      if (i == lsize) return ptt(t->key, lsum + t->left->sum);
      if (i < lsize)
	t = t->left;
      else {
	i -= lsize + 1;
	lsum += t->key + t->left->sum;
	t = t->right;
      }
    }
    return ptt(TINF, 0);
  }

  void print(node t, int k, int indent) {
    if (t == nullnode) return;
    if (t != NULL) {
      for (int i = 0; i < indent; i++) putchar(' '), putchar(' ');
      t->print(k + t->left->size);
      print(t->left, k, indent + 1);
      print(t->right, k + t->left->size + 1, indent + 1);
    }
  }
  void print() { print(root, 0, 0); }

  void inorder(node t) {
    if (t != nullnode && t != NULL) {
      inorder(t->left);
      cout << t->key << ' ';
      inorder(t->right);
    }
  }
  void inorder() {
    inorder(root);
    cout << endl;
  }
};

/* global variables */

int as[MAX_N];
TreapSum<ll,MAX_N> trp(LINF);

/* subroutines */

/* main */

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &as[i]);

  if (k == 1) {
    puts("0");
    return 0;
  }
  
  for (int i = 0; i < k - 1; i++) trp.insert(as[i]);

  int hk = (k - 1) / 2;
  ll mind = LINF;

  for (int i = 0, j = k - 1; j < n; i++, j++) {
    trp.insert(as[j]);
    ll asum = trp.sum();

    for (int dk = 0; dk < 2; dk++) {
      int hk0 = hk + dk;
      pll r = trp.findat(hk0);
      ll &a0 = r.first, &lsum = r.second;
      ll d = ((asum - lsum) - a0 * (k - hk0)) - (lsum - a0 * hk0);
      if (mind > d) mind = d;
      //printf("%d-%d: hk0=%d, asum=%lld, lsum=%lld, a0=%lld, d=%lld\n",
      //i, j, hk0, asum, r.second, a0, d);
    }

    trp.remove(as[i]);
  }

  printf("%lld\n", mind);
  return 0;
}
0