結果

問題 No.2408 Lakes and Fish
コンテスト
ユーザー vjudge1
提出日時 2025-08-13 11:31:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 203 ms / 2,000 ms
コード長 1,219 bytes
コンパイル時間 2,001 ms
コンパイル使用メモリ 200,864 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-13 11:31:20
合計ジャッジ時間 6,243 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//B;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll n, m; cin>>n>>m;
    vector<ll> L;
    vector<pair<ll, pair<ll, ll>>> F(m+1);

    L.push_back(LLONG_MIN);
    for(ll i = 1; i<=n; i++) {
        ll x; cin>>x;
        L.push_back(x);
    }
    L.push_back(LLONG_MAX);

    for(ll i = 1; i<=m; i++) {
        ll Fi, B, W; cin>>Fi>>B>>W;
        F[i] = {Fi, {B, W}};
    }

    ll ans = 0;
    for(ll i = 1; i<=m; i++) {
        //find L[i] yang lebih dekat ke Fi
        //Binary search
        //lower bound -> nilai pertama yg >=value
        //upper bound -> nilai pertama yg >value
        ll Fi = F[i].first;
        ll B = F[i].second.first;
        ll W = F[i].second.second;
        
        ll idx = lower_bound(L.begin(), L.end(), Fi)-L.begin();
     

        ll c1 = L[idx];
        ll c2 = L[idx-1];
 

        ll pohonTerdekat = 
        (abs(c1-Fi) < abs(c2-Fi) ? c1 : c2);

        ll move = W - abs(pohonTerdekat - Fi);

        ll stay = (binary_search(L.begin(), L.end(), Fi) ? W:B); 
        //tetap, tidak pindah
        //jika posisinya sdh tertutup pohon maka W
        //jika blm maka B

        ans += max(move, stay);
    }

    cout<<ans<<"\n";



}
0