結果

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

ソースコード

diff # 

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

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

    for(ll i = 1; i<=n; i++) {
        cin>>L[i];
    }

    L[0] = LLONG_MIN;
    L[n+1] = 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