結果

問題 No.2408 Lakes and Fish
ユーザー vjudge1
提出日時 2025-08-13 11:17:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,038 bytes
コンパイル時間 1,997 ms
コンパイル使用メモリ 199,700 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-13 11:17:44
合計ジャッジ時間 6,434 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 2
other AC * 1 RE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

//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++) {
        cin>>L[i];
    }
    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++) {
        //how to find L[i] yang lebih dekat ke F[i].first?
        //Binary search? atau upper lower bound
        //lower bound -> nilai pertama yg >=value
        //upper bound -> nilai pertama yg >value
        ll idx = lower_bound(L.begin(), L.end(), F[i].first)-L.begin();
     

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

        ll pohonTerdekat = 
        (abs(c1-F[i].first) < abs(c2-F[i].first) ? c1 : c2);

        ll cmp1 = F[i].second.second - abs(pohonTerdekat - F[i].first);
        ll cmp2 = F[i].second.first;

        ans += max(cmp1, cmp2);
    }

    cout<<ans<<"\n";



}
0