結果
問題 | No.2744 Power! or +1 |
ユーザー |
|
提出日時 | 2024-04-18 16:03:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,084 ms / 3,000 ms |
コード長 | 1,849 bytes |
コンパイル時間 | 2,323 ms |
コンパイル使用メモリ | 200,416 KB |
最終ジャッジ日時 | 2025-02-21 03:01:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define REP(i, n) for(ll i = 0;i < n;i++)#define REPR(i, n) for(ll i = n;i >= 0;i--)#define FOR(i, m, n) for(ll i = m;i < n;i++)#define FORR(i, m, n) for(ll i = m;i >= n;i--)#define REPO(i, n) for(ll i = 1;i <= n;i++)#define ll long long#define INF (ll)1ll << 60#define MINF (-1 * INF)#define ALL(n) n.begin(),n.end()#define MOD (ll)1000000007#define P pair<ll, ll>ll d[410000]; // 結果struct edge { ll to, cost; };vector<edge> g[410000]; //隣接リスト to, costvoid dijkstra(ll a) { //だいくすとら!priority_queue<P, vector<P>, greater<P> > q;fill(d, d + 410000, INF);d[a] = 0;q.push(P(0, a));while (!q.empty()) {P p = q.top();q.pop();ll v = p.second;if (d[v] < p.first) continue;REP(i, g[v].size()) {edge e = g[v][i];if (d[e.to] > d[v] + e.cost) {d[e.to] = d[v] + e.cost;q.push(P(d[e.to], e.to));}}}}ll n, a, b, c, u = 210000;int main(){cin >> n >> a >> b >> c;REP(i, n){g[i].push_back({(i + 1) % n, a});g[i + u].push_back({(i + 1) % n + u, a});ll now = i, cost = b;bool overn = false;if (i <= 1) continue;while(cost <= 4 * 1e10){now *= i;cost *= b;if (now >= n) overn = true;now %= n;g[i].push_back({(overn ? u + now : now), cost});g[u + i].push_back({u + now, cost});}}ll now = 1;bool overn = false;REPO(i, n - 1){now *= i;if (now >= n) overn = true;now %= n;g[i].push_back({(overn ? u + now : now), c});g[u + i].push_back({0, c});}dijkstra(1);cout << min(d[0], d[u]) << endl;}