結果

問題 No.2408 Lakes and Fish
コンテスト
ユーザー vjudge1
提出日時 2024-05-01 23:40:55
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 192 ms / 2,000 ms
コード長 1,879 bytes
コンパイル時間 2,157 ms
コンパイル使用メモリ 164,968 KB
実行使用メモリ 19,016 KB
最終ジャッジ日時 2024-11-22 07:56:07
合計ジャッジ時間 5,484 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define ll      long long
#define pii     pair <int, int> 
#define pb      push_back
#define mp      make_pair
#define dbg     puts("dbg");
#define outp(x) cout << #x << " = " << (x) << endl
#define all(x)  (x).begin(), (x).end()
#define test    int t; cin >> t; while(t--){solve();}
#define MOD     998244353
int fpb(int a,int b){if(b == 0){return a;}return fpb(b, a%b);}
int kpk(int a,int b){return (a*b)/fpb(a, b);}

int n, m, l[100002];
map <int, int> ada;

struct fish{
    int koordinat, kena, gakena;
};

fish ikan[100002];

void solve(){   
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> l[i];
        ada[l[i]] = 1;
    }
    int cnt = 0, tot = 0;
    for(int i=1; i<=m; i++){
        cin >> ikan[i].koordinat >> ikan[i].kena >> ikan[i].gakena;
        if(ada[ikan[i].koordinat]){
            tot += ikan[i].gakena;
        } else {
            int indeksUB = upper_bound(l+1, l+n+1, ikan[i].koordinat) - l;
            int majuOperasi = l[indeksUB] - ikan[i].koordinat;
            int mundurOperasi = ikan[i].koordinat - l[indeksUB-1];
            int stayPosisiOperasi = 0;
            int majuMagis = ikan[i].gakena;
            int mundurMagis = ikan[i].gakena;
            int stayPosisiMagis = ikan[i].kena;
            if(indeksUB == n+1){
                majuOperasi = 2e18;
            } else if(indeksUB == 1){
                mundurOperasi = 2e18;
            }
            int finalMaju = majuMagis - majuOperasi, finalMundur = mundurMagis - mundurOperasi;
            int finalStay = stayPosisiMagis - stayPosisiOperasi;
            int maxi = max(finalMaju, max(finalStay, finalMundur));
            tot += maxi;
        }
    }       
    cout << tot << endl;
}


int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}
0