Submission #2099930

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://arc063.contest.atcoder.jp/tasks/arc063_b>
問題文============================================================
 N 個の町が一直線上に並んでいます。
 行商人の高橋君は町 1 から出発し、リンゴの売買をしながら町 N へと向かいます。
 
 はじめ高橋君は町 1 におり、リンゴを 1 つも持っていません。
 高橋君は次のいずれかの行動を繰り返し行います。
 
 移動: 町 i (i<N) にいるとき、町 i+1 へ移動する。
 リンゴの売買: リンゴを好きな個数だけ売買する。
 ここで、町 i (1≦i≦N) ではリンゴの買値も売値もともに Ai 円とする。ここで Ai は相異なる整数です。
 1 つの町で売買するリンゴの個数に制限はありませんが、
 旅の中で売買するリンゴの個数は合計で (買う個数と売る個数を合わせて) T 個以下にしなくてはなりません。
 
 高橋君は旅の利益、すなわちリンゴを売った代金から買った代金を引いた値を最大にするように旅をするとします。
 旅が終わったときに持っていたリンゴの価値は考えず、旅の中で売買した金額だけを考えます。
 
 この旅に先立って、
 青木君は任意の町 i に対して Ai を好きな非負整数 Ai' に変えるという操作を好きなだけ行うことができます。
 ただし、この操作は行うごとに |Ai−Ai'| のコストがかかります。
 操作後には異なる町の間でリンゴの値段が同じになっていても構いません。
 
 青木君の目的はできるだけ少ない合計コストの操作で高橋君の利益を少なくとも 1 円下げることです。
 合計コストの最小値を求めてください。
 
 ただし、元の状態で高橋君が 1 円以上の利益を上げられることは仮定して構いません。
 

=================================================================

解説=============================================================

================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N,T; cin >> N >> T;
    vector<ll> A(N);
    for(auto &in:A) cin >> in;
    ll minv = A[0], maxdiff = -LINF;
    for(int i = 0; i < N;i++){
        minv = min(A[i],minv);
        maxdiff = max(maxdiff,A[i] - minv);
    }
    
    ll maxdiff_cnt = 0;
    minv = A[0];
    for(int i = 0; i < N;i++){
        minv = min(A[i],minv);
        if(A[i] - minv == maxdiff) maxdiff_cnt++;
    }
    cout << min(maxdiff_cnt,T/2) << endl;
	return 0;
}

Submission Info

Judge Result