結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2018-09-29 00:07:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,144 bytes |
コンパイル時間 | 1,118 ms |
コンパイル使用メモリ | 85,416 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 07:40:30 |
合計ジャッジ時間 | 6,205 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 81 WA * 6 |
ソースコード
#include <iostream> #include <stdio.h> #include <string> #include <vector> #include <set> #include <cmath> #include <algorithm> #include <cstdio> #include <queue> #include <map> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pint; typedef pair<double,int> pdi; #define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i) #define REPR(i, n) for(ll i = n;i >= 0;i--) #define FOR(i, m, n) for(ll i = m;i < n;i++) int N,K; vector<int> aa; ll f(ll m){ ll tmp=0,ans; REP(i,K){tmp += abs(aa[i]-m);} ans = tmp; int l = 0; for (int r = K; r < N; r++) { tmp += abs(aa[r]-m); tmp -= abs(aa[l]-m); ans = min(tmp,ans); l ++; } return ans; } int main(void) { cin >> N >> K; int a; REP(i,N){ cin >> a; aa.push_back(a); } f(3); ll x0,x1,x2,x3; x0 = 0; x3 = pow(10,9)+10; x1 = (x0*2+x3)/3; x2 = (x0+x3*2)/3; ll y0,y1,y2,y3; for (int i = 0; i < 55; i++) { y1 = f(x1); y2 = f(x2); if(y1>y2){ x0 = x1; }else{ x3 = x2; } x1 = (x0*2+x3)/3; x2 = (x0+x3*2)/3; } cout << min(min(f(x0),y1),min(y2,f(x3))) << endl; }