#939099 (C++17(clang)) No.2591 安上がりな括弧列

提出ソース

結果

問題	No.2591 安上がりな括弧列
ユーザー	Oji Coder
提出日時	2023-12-19 03:46:00
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	5,738 bytes
コンパイル時間	1,456 ms
コンパイル使用メモリ	135,552 KB
実行使用メモリ	6,676 KB
最終ジャッジ日時	2023-12-19 03:46:03
合計ジャッジ時間	2,375 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	2 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	1 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	1 ms 6,676 KB
testcase_08	AC	2 ms 6,676 KB
testcase_09	AC	1 ms 6,676 KB
testcase_10	AC	2 ms 6,676 KB
testcase_11	AC	5 ms 6,676 KB
testcase_12	AC	5 ms 6,676 KB
testcase_13	AC	5 ms 6,676 KB
testcase_14	AC	5 ms 6,676 KB
testcase_15	AC	5 ms 6,676 KB
testcase_16	AC	5 ms 6,676 KB
testcase_17	AC	2 ms 6,676 KB
testcase_18	AC	3 ms 6,676 KB
testcase_19	AC	3 ms 6,676 KB
testcase_20	AC	5 ms 6,676 KB
testcase_21	AC	5 ms 6,676 KB
testcase_22	AC	5 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*
g++ -O2 --std=c++17 -D LOCAL A.cpp
*/

#include <iostream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <utility>
#include <limits.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

#ifdef LOCAL
#define dlog(x) { cerr << '[' << __LINE__ << "] " << x << endl; }
#define dvar(v) { cerr << '[' << __LINE__ << "] " << #v << " = " << v << endl; }
#define dvec(c) { cerr << '[' << __LINE__ << "] " << #c << " = "; for (int i = 0; i < c.size(); ++i) if (i == 0) cerr << '['<<i<<']'<<c[i]; else cerr << " ["<<i<<']'<<c[i]; cerr << endl; } 
#define dmap(m) { cerr << '[' << __LINE__ << "] " << #m << " = "; for (auto it: m) cerr << it.first << "=>" << it.second << ' '; cerr << endl; }
#define dset(s) { cerr << '[' << __LINE__ << "] " << #s << " = "; for (auto item: s) cerr << item << ' '; cerr << endl; }
#else
#define dlog(x)
#define dvar(v)
#define dvec(c)
#define dmap(m)
#define dset(s)
#endif

#define rep(i,n) for (int i = 0; i < int(n); ++i)
#define repr(i,from,to) for (int i = int(from); i <= int(to); ++i)
#define rrep(i,n) for (int i = (n)-1; 0 <= i; --i)
#define rrepr(i,from,to) for (int i = int(from); int(to) <= i; --i)
#define endl '\n'

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 

typedef pair<int, int> P;
typedef pair<LL, LL> LP;
#ifndef F
#define F first
#define S second
#endif 

#ifndef umap
#define umap unordered_map
#endif
#ifndef uset
#define uset unordered_set
#endif

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  return os << p.F << ':' << p.S;
}


/*
  == AC Library Cheat sheet
  documentation: file:///Users/nobu/Downloads/ac-library/document_ja/index.html

  mint
    mint m.pow(int p)  //! return m^p
    mint m.inv() //! returns i that gives (m * i).val() == 1 
    int m.val() 

  fenwick_tree (BIT)
    fenwick_tree<T> fw(int n) //! init a[0] .. a[n-1] with all 0
    void fw.add(int idx, T x); //! a[idx] += x
    T fw.sum(int l, int r); //! return a[l] + .. + a[r-1]

  dsu (UnionFind)
    dsu d(int n)  //! prepare dsu with n nodes
    void d.merge(int x, int y)  //! connect node x and y
    bool d.same(int x, int y)  //! return true if node x and y are connected
    int d.leader(int x)  //! return the leader node of the connected group
    int d.size(int x) //! return the size of the group that node x belongs to
    vector<vector<int>> d.groups() //! return a vector of vectors that contain the nodes in each group

  scc_graph
    scc_graph　g(int n)  //! create a directed graph with n nodes
    g.add_edge(int from, int to)  //! create a directed edge from node from to node to
    vector<vector<int>> g.scc()  //! return the vector of strongly connected components that are topologically sorted

  segtree
    segtree<S, op, e>
      S: type of the monoid 
      op: function to return the product of two elements
      e: function to return the identity element such that op(x, e) == x fo any x 

  lazy_segtree
    lazy_segtree<S, op, e, F, mapping, composition, id>
      F: type of parameters to define the operation applied to the target elements
      mapping: function to return the element after applying the operation to the target element
      composition: function to combine the two sets of operation parameters to one
      id: function to return the operation parameter i such that mapping(i, x) = x for any x

      using S = int;
      S op(S a, S b) { return min(a, b); }
      S e() { return INF; }
      using F = int;
      S mapping(F f, S x) { return min(f, x); }
      F composition(F f, F g) { return min(f, g); }
      F id() { return INF; }

*/

// int dx[] = { 0, -1, 1, 0 };
// int dy[] = { -1, 0, 0, 1 };

// int dx[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// int dy[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

const int INF = 2e9+1e4;
const LL INFL = 4e18+1e9;
const int MOD = 998244353;

// #define USE_ACL
#ifdef USE_ACL

#include <atcoder/all>
using namespace atcoder;

using mint = static_modint<MOD>;

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < MOD);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    if ((int)fact.size() <= n) return smallk(n, k);
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint smallk(int n, int k) {
    if (n-k < k) k = n-k;
    assert(k < (int)fact.size());
    mint ret = 1;
    for (int i = n-k+1; i <= n; ++i) ret *= i;
    return ret*ifact[k];
  }
};

ostream& operator<<(ostream& os, const mint& i) {
  return os << i.val();
}

#endif




int main()
{
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << setprecision(20);

  int n;
  string s;
  cin >> n >> s;
  vector<int> a(2*n);
  rep(i, 2*n) cin >> a[i];

  vector<LL> dp(n+1, INFL);
  dp[0] = 0;
  rep(i, 2*n) {
    vector<LL> next(n+1, INFL);
    if (s[i] == '(') {
      rep(j, n) chmin(next[j+1], dp[j]);
      repr(j, 1, n) chmin(next[j-1], dp[j]+a[i]);
    } else if (s[i] == ')') {
      rep(j, n) chmin(next[j+1], dp[j]+a[i]);
      repr(j, 1, n) chmin(next[j-1], dp[j]);
    }
    dp.swap(next);
  }
  cout << dp[0] << endl;

  cout << flush;
  return 0;
}

yukicoder

結果

テストケース

ソースコード