結果

問題 No.2408 Lakes and Fish
ユーザー vjudge1vjudge1
提出日時 2024-05-01 23:40:55
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 1,879 bytes
コンパイル時間 1,757 ms
コンパイル使用メモリ 164,328 KB
実行使用メモリ 19,048 KB
最終ジャッジ日時 2024-05-01 23:41:02
合計ジャッジ時間 4,607 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 113 ms
19,012 KB
testcase_05 AC 122 ms
19,048 KB
testcase_06 AC 83 ms
12,672 KB
testcase_07 AC 149 ms
19,012 KB
testcase_08 AC 146 ms
18,944 KB
testcase_09 AC 152 ms
18,944 KB
testcase_10 AC 145 ms
18,944 KB
testcase_11 AC 64 ms
10,752 KB
testcase_12 AC 101 ms
14,848 KB
testcase_13 AC 23 ms
6,940 KB
testcase_14 AC 49 ms
10,436 KB
testcase_15 AC 107 ms
15,360 KB
testcase_16 AC 39 ms
8,704 KB
testcase_17 AC 27 ms
6,944 KB
testcase_18 AC 67 ms
11,392 KB
testcase_19 AC 103 ms
14,536 KB
testcase_20 AC 74 ms
12,288 KB
testcase_21 AC 105 ms
14,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#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