提出 #53348729

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e17;

void solve() {
    int n, m; long long c;
    cin >> n >> c >> m;

    // dp[i] is the maximum profit that you can gain with the markets seen so
    // far such that you are currently in the i-th market.
    vector<long long> dp(n, -inf);
    dp[0] = 0;

    for(int j = 0; j < m; j++) {
        int t; long long p;
        cin >> t >> p;
        t--;

        auto ndp = dp;
        for(int i = 0; i < n; i++) {
            ndp[t] = max(ndp[t], dp[i] - c*abs(i - t) + p);
        }
        swap(dp, ndp);
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
}

int main() {
    solve();
}

提出情報

提出日時
問題 G - Merchant Takahashi
ユーザ adaptatron
言語 C++ 20 (gcc 12.2)
得点 0
コード長 704 Byte
結果 TLE
実行時間 2212 ms
メモリ 6572 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 550
結果
AC × 4
AC × 7
TLE × 62
セット名 テストケース
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt, 01_random_56.txt, 01_random_57.txt, 01_random_58.txt, 01_random_59.txt, 01_random_60.txt, 01_random_61.txt, 01_random_62.txt, 01_random_63.txt, 01_random_64.txt, 01_random_65.txt, 01_random_66.txt, 01_random_67.txt, 01_random_68.txt
ケース名 結果 実行時間 メモリ
00_sample_00.txt AC 1 ms 3488 KiB
00_sample_01.txt AC 1 ms 3492 KiB
00_sample_02.txt AC 1 ms 3528 KiB
00_sample_03.txt AC 1 ms 3592 KiB
01_random_04.txt TLE 2207 ms 6432 KiB
01_random_05.txt TLE 2207 ms 6320 KiB
01_random_06.txt TLE 2207 ms 6560 KiB
01_random_07.txt TLE 2207 ms 6320 KiB
01_random_08.txt TLE 2207 ms 6408 KiB
01_random_09.txt TLE 2207 ms 6348 KiB
01_random_10.txt TLE 2210 ms 6404 KiB
01_random_11.txt TLE 2207 ms 6400 KiB
01_random_12.txt TLE 2207 ms 6352 KiB
01_random_13.txt TLE 2207 ms 6460 KiB
01_random_14.txt TLE 2207 ms 6380 KiB
01_random_15.txt TLE 2207 ms 6328 KiB
01_random_16.txt TLE 2207 ms 6396 KiB
01_random_17.txt TLE 2208 ms 6412 KiB
01_random_18.txt TLE 2207 ms 6320 KiB
01_random_19.txt TLE 2207 ms 6372 KiB
01_random_20.txt TLE 2207 ms 6436 KiB
01_random_21.txt TLE 2207 ms 6280 KiB
01_random_22.txt TLE 2207 ms 6484 KiB
01_random_23.txt TLE 2207 ms 6472 KiB
01_random_24.txt TLE 2207 ms 6324 KiB
01_random_25.txt TLE 2208 ms 6340 KiB
01_random_26.txt TLE 2207 ms 6324 KiB
01_random_27.txt TLE 2207 ms 6436 KiB
01_random_28.txt TLE 2207 ms 6336 KiB
01_random_29.txt TLE 2207 ms 6400 KiB
01_random_30.txt TLE 2207 ms 6340 KiB
01_random_31.txt TLE 2207 ms 6432 KiB
01_random_32.txt TLE 2207 ms 6380 KiB
01_random_33.txt TLE 2207 ms 6400 KiB
01_random_34.txt TLE 2207 ms 6400 KiB
01_random_35.txt TLE 2211 ms 6480 KiB
01_random_36.txt TLE 2207 ms 6484 KiB
01_random_37.txt TLE 2208 ms 6348 KiB
01_random_38.txt TLE 2208 ms 6396 KiB
01_random_39.txt TLE 2207 ms 6404 KiB
01_random_40.txt TLE 2207 ms 6344 KiB
01_random_41.txt TLE 2208 ms 6400 KiB
01_random_42.txt TLE 2207 ms 6440 KiB
01_random_43.txt TLE 2207 ms 6404 KiB
01_random_44.txt TLE 2208 ms 6384 KiB
01_random_45.txt TLE 2207 ms 6572 KiB
01_random_46.txt TLE 2207 ms 6432 KiB
01_random_47.txt TLE 2208 ms 6328 KiB
01_random_48.txt TLE 2207 ms 6320 KiB
01_random_49.txt TLE 2207 ms 6488 KiB
01_random_50.txt TLE 2207 ms 6324 KiB
01_random_51.txt TLE 2208 ms 6572 KiB
01_random_52.txt TLE 2210 ms 4460 KiB
01_random_53.txt TLE 2207 ms 5312 KiB
01_random_54.txt TLE 2207 ms 4940 KiB
01_random_55.txt AC 279 ms 3620 KiB
01_random_56.txt TLE 2207 ms 5288 KiB
01_random_57.txt TLE 2210 ms 4528 KiB
01_random_58.txt TLE 2207 ms 5844 KiB
01_random_59.txt TLE 2207 ms 5024 KiB
01_random_60.txt TLE 2207 ms 6212 KiB
01_random_61.txt TLE 2211 ms 6404 KiB
01_random_62.txt TLE 2207 ms 3940 KiB
01_random_63.txt TLE 2207 ms 6396 KiB
01_random_64.txt TLE 2212 ms 5692 KiB
01_random_65.txt TLE 2207 ms 5740 KiB
01_random_66.txt TLE 2207 ms 3468 KiB
01_random_67.txt AC 82 ms 3460 KiB
01_random_68.txt AC 82 ms 3484 KiB