結果
問題 | No.2057 Ising Model |
ユーザー |
![]() |
提出日時 | 2022-09-04 05:08:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 1,069 ms |
コンパイル使用メモリ | 80,692 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-17 23:07:17 |
合計ジャッジ時間 | 2,169 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 44 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; vector<vector<ll>> matpow(vector<vector<ll>> a, ll x){ vector<vector<ll>> res(a.size(), vector<ll>(a.size(), 1LL << 60)); for(int i = 0; i < a.size(); i++) res[i][i] = 0; for(; x > 0; x >>= 1){ if(x & 1){ vector<vector<ll>> nres(a.size(), vector<ll>(a.size(), 1LL << 30)); for(int i = 0; i < a.size(); i++){ for(int j = 0; j < a.size(); j++){ for(int k = 0; k < a.size(); k++){ nres[i][j] = min(nres[i][j], res[i][k]+a[k][j]); } } } res = nres; } vector<vector<ll>> na(a.size(), vector<ll>(a.size(), 1LL << 60)); for(int i = 0; i < a.size(); i++){ for(int j = 0; j < a.size(); j++){ for(int k = 0; k < a.size(); k++){ na[i][j] = min(na[i][j], a[i][k]+a[k][j]); } } } a = na; } return res; } int main(){ ll n, a, b; cin >> n >> a >> b; vector<vector<ll>> mat(2, vector<ll>(2)); mat[0][0] = a+b; mat[0][1] = -a+b; mat[1][0] = -a-b; mat[1][1] = a-b; auto res = matpow(mat, n-1); ll ans1 = min(res[0][0]+b, res[0][1]-b); ll ans2 = min(res[1][0]+b, res[1][1]-b); cout << min(ans1, ans2) << endl; return 0; }