結果

問題 No.1297 銅像
ユーザー 👑 tatyamtatyam
提出日時 2020-09-12 20:43:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,219 bytes
コンパイル時間 3,053 ms
コンパイル使用メモリ 215,952 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-30 19:01:31
合計ジャッジ時間 8,366 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 31 ms
4,376 KB
testcase_07 AC 31 ms
4,380 KB
testcase_08 AC 31 ms
4,376 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
template<class T> inline void chmin(T& a, const T& b){ if(a > b) a = b; }

u32 scan_u32(){
    u32 x = 0;
    char c;
    while(c = getchar_unlocked() ^ 48, c < 10) x = x * 10 + c;
    return x;
}
u64 scan_u64(){
    u64 x = 0;
    char c;
    while(c = getchar_unlocked() ^ 48, c < 10) x = x * 10 + c;
    return x;
}
signed main(){
    u32 n = scan_u32(), c = scan_u32();
    u64 a[n + 1], b[n + 1];
    for(u32 i = 1; i <= n; i++){
        a[i] = scan_u64();
        b[i] = scan_u64();
    }
    u64 dp1[n + 1], dp2[n + 1];
    memset(dp1, 0xff, sizeof(dp1));
    memset(dp2, 0xff, sizeof(dp2));
    dp2[0] = 0;
    for(u32 i = 1; i <= n; i++){
        u64 tri = 0;
        for(u32 j = i; j--; ){
            chmin(dp1[i], dp2[j] + b[i] + a[i] * (i - j) + c * tri);
            tri += i - j;
        }
        tri = 0;
        for(u32 j = i; j; j--){
            chmin(dp2[i], dp1[j] + a[j] * (i - j) + c * tri);
            tri += i - j + 1;
        }
    }
    cout << dp2[n] << '\n';
}
0