結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー chocono2230chocono2230
提出日時 2020-06-26 23:59:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 78 ms / 2,000 ms
コード長 1,461 bytes
コンパイル時間 1,602 ms
コンパイル使用メモリ 170,856 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-05 01:07:10
合計ジャッジ時間 3,698 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:27:3: warning: 'mni' may be used uninitialized [-Wmaybe-uninitialized]
   27 |   if(mni != 0 && mni != n-1){
      |   ^~
main.cpp:18:17: note: 'mni' was declared here
   18 |   int mn = INF, mni;
      |                 ^~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

const int INF = 1001001001;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  int mn = INF, mni;
  rep(i, n){
    cin >> a.at(i);
    if(mn > a.at(i)){
      mn = a.at(i);
      mni = i;
    }
  }
  int ans = INF;
  if(mni != 0 && mni != n-1){
    int lmn = INF, rmn = INF;
    rep(i, mni){
      lmn = min(lmn, a.at(i));
    }
    rep2(i, mni+1, n){
      rmn = min(rmn, a.at(i));
    }
    ans = lmn + rmn + mn;
  }
  vector<int> smn(n, INF);
  smn.back() = a.back();
  smn.front() = a.front();
  rrep2(i, mni, n-1){
    smn.at(i) = min(a.at(i), smn.at(i+1));
  }
  rep2(i, 1, mni){
    smn.at(i) = min(a.at(i), smn.at(i-1));
  }
  
  rrep2(i, mni+1, n-1){
    if(a.at(i) < smn.at(i+1)) continue;
    int add = mn + a.at(i) + smn.at(i+1);
    ans = min(ans, add);
  }
  rrep2(i, 1, mni){
    if(a.at(i) < smn.at(i-1)) continue;
    int add = mn + a.at(i) + smn.at(i-1);
    ans = min(ans, add);
  }
  if(ans == INF) ans = -1;
  cout << ans << endl;

  return 0;
}
0