結果

問題 No.1297 銅像
コンテスト
ユーザー 👑 tatyam
提出日時 2020-09-12 20:43:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,219 bytes
コンパイル時間 3,440 ms
コンパイル使用メモリ 217,100 KB
最終ジャッジ日時 2025-01-14 13:44:24
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

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