結果

問題 No.2408 Lakes and Fish
ユーザー vjudge1vjudge1
提出日時 2024-05-01 23:40:55
言語 C++17(clang)
(17.0.6 + boost 1.83.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
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 123 ms
18,944 KB
testcase_05 AC 123 ms
18,944 KB
testcase_06 AC 90 ms
12,672 KB
testcase_07 AC 188 ms
18,816 KB
testcase_08 AC 192 ms
19,016 KB
testcase_09 AC 192 ms
18,944 KB
testcase_10 AC 178 ms
18,944 KB
testcase_11 AC 77 ms
10,752 KB
testcase_12 AC 124 ms
14,848 KB
testcase_13 AC 28 ms
6,656 KB
testcase_14 AC 63 ms
9,472 KB
testcase_15 AC 134 ms
15,360 KB
testcase_16 AC 47 ms
8,704 KB
testcase_17 AC 28 ms
6,656 KB
testcase_18 AC 75 ms
11,520 KB
testcase_19 AC 124 ms
14,208 KB
testcase_20 AC 86 ms
12,160 KB
testcase_21 AC 132 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