Contest Duration: - (local time) (100 minutes) Back to Home

Submission #6814868

Source Code Expand

Copy
#if 1
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <set>
#include <map>
#include <numeric>
#include <cassert>
#include <iomanip>
#define _SCL_SECURE_NO_WARNINGS
#include "boost/multiprecision/cpp_int.hpp"

#pragma warning (disable:4244)

using namespace std;

using int128 = boost::multiprecision::int128_t;
#if 0
#define int boost::multiprecision::int128_t
#else
#define int long long
#endif
#if 0
constexpr long long MOD = 1000000007LL;
#else
constexpr long long MOD = 998244353LL;
#endif
constexpr long long INF = 1145141919810893LL;

//
#if 1

//ダイクストラ法を使うときはTとしてこれを継承したものを使う
struct Dijk {
int dijk;
};
struct Edge {
int next;
int w = 1;
};
template<class T>
struct Vertex {
std::vector<Edge>edges;
T val;
};
template<class T>
struct Graph {
std::vector<Vertex<T>> vertex;
public:
Graph(size_t nVertex = 0) :vertex(nVertex) {
}
void setArray(int u, int v, int w = 1) {
vertex[u].edges.push_back(Edge{ v ,w });
}
void setConnect(int u, int v, int w = 1) {
setArray(u, v, w);
setArray(v, u, w);
}
T& val(int u) {
return vertex[u].val;
}
void dfsImpl(int pos, int prev, std::function<bool(int now, int next, int w)> func) {
for (auto& e : vertex[pos].edges) {
if (e.next == prev) continue;
if (func(pos, e.next, e.w)) {
dfsImpl(e.next, pos, func);
}
//ここに追加する場合も
}
}
void dfsCustom(int pos, int prev);
//深さ優先探索
void dfs(int pos, std::function<bool(int now, int next, int w)> func) {
dfsImpl(pos, -1, func);
}
//幅優先探索
void bfs(int pos, std::function<bool(int now, int next, int w)> func) {
std::unordered_set<int> set;
set.insert(pos);
while (!set.empty()) {
std::unordered_set<int> setNew;
for (auto& one : set) {
for (auto& e : vertex[one].edges) {
if (func(one, e.next, e.w)) {
setNew.insert(e.next);
}
}
}
set = setNew;
}
}
//
void dijkstra(int pos) {
for (int i = 0; i < vertex.size(); ++i) {
val(i).dijk = -1;
}
val(pos).dijk = 0;
//
bfs(pos, [&](int now, int next, int w) {
if (val(next).dijk<0 || val(next).dijk>val(now).dijk + w) {
val(next).dijk = val(now).dijk + w;
return true;
}
return false;
});
}
int farestID = -1;
int far = -1;
val(pos) = 0;
//dfsで正しい？？
dfs(pos, [&](int now, int next, int w) {
val(next) = 1 + val(now);
if (val(next) > far) {
far = val(next);
farestID = next;
}
});
return { farestID, far };
}
if (vertex.size() <= 1)return 0;
return res.second;
}
};
#endif

//////////////////////////////////
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
int sign(int x) {
if (x > 0)return 1;
if (x < 0)return -1;
return 0;
}
//マイナスでも動作するmod(いちいち手で書くとunsignedの引き算オーバーフローで死にやすい)
int mod(int n, int m) {
assert(0 < m);	//さすがに割る数は正でないといけない
return (n % m + m) % m;
}

//約数
std::vector<int> divisor(int n) {
std::vector<int> ret;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) {
ret.push_back(n / i);
}
}
}
return ret;
}

bool isPrime(int n) {
if (n <= 1)return false;
if (n == 2)return true;
if (n % 2 == 0)return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0)return false;
}
return true;
}

////////////////////////
#if 1
//二項係数、int128は使わなく64で十分
class Combination {
std::vector<long long>fac, finv, inv;
public:
Combination(long long N) :fac(N + 1), finv(N + 1), inv(N + 1) {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (long long i = 2; i < N + 1; i++) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
long long get(long long n, long long k) {
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
};

#endif
#if 1

int modInv(int a) {
int b = MOD, u = 1, v = 0;
while (b) {
int t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= MOD;
if (u < 0) u += MOD;
return u;
}

template <class T>
void modify(T& n, T mod = MOD) {
if (n < 0) {
n %= mod;
n += mod;
}
n %= mod;
}

#endif

//文字列の置き換え(遅い？)
int replace(std::string* str, const std::string& old_, const std::string& new_) {
std::string& String1 = *str;
//String1.reserve(str->size() * new_.size() / old_.size() + 1);
std::string::size_type  Pos(String1.find(old_));
int result = 0;
while (Pos != std::string::npos) {
result++;
String1.replace(Pos, old_.length(), new_);
Pos = String1.find(old_, Pos + new_.length());
}
return result;
}

#define ALL(t) t.begin(), t.end()

//LIS(最長増加部分列)
//eq = falseで狭義増加(1,3,7,9...)
//eq = trueで広義増加(1,1,3,7,7,7,7,9...)
std::vector<int> lis(const std::vector<int>& ary, bool eq = false) {
std::vector<int>dp(ary.size());
constexpr int intMax = std::numeric_limits<int>::max();
fill(ALL(dp), intMax);
for (int i = 0; i < ary.size(); ++i) {
auto itr = std::lower_bound(ALL(dp), ary[i] + (eq ? 1 : 0));
*itr = ary[i];
}
auto itr = std::lower_bound(ALL(dp), intMax);
dp.resize(itr - dp.begin());
return dp;
}

//座標圧縮:O(NlogN)
struct Compressor {
std::set<int> buf;
std::unordered_map<int, int>res;
public:
template <class... Args>
void insert(Args... args) {
buf.insert(args...);
}
void calc() {
res.clear();
int i = 0;
for (auto& one : buf) {
res[one] = i;
++i;
}
}
int get(int n) const {
return res.at(n);
}
std::vector<int> get(const std::vector<int>& v) const {
std::vector<int> res(v.size());
for (int i = 0; i < v.size(); ++i) {
res[i] = get(v[i]);
}
return res;
}
};

//MODで割ったあまりの演算
struct Rational {
int r;
Rational(int rr) :r(rr) {
}
operator int() {
return r;
}
Rational operator+(const Rational& other)const {
Rational res(0);
res.r = r + other.r;
modify(res.r);
return res;
}
Rational operator-(const Rational& other)const {
Rational res(0);
res.r = r - other.r;
modify(res.r);
return res;
}
Rational operator*(const Rational& other) const {
Rational res(0);
res.r = r * other.r;
modify(res.r);
return res;
}
Rational operator/(const Rational& other)const {
Rational res(0), res1(0);
res = *this;
res1.r = modInv(other.r);
res = (*this) * res1;
modify(res.r);
return res;
}
void operator+=(const Rational& other) {
*this = *this + other;
}
void operator-=(const Rational& other) {
*this = *this - other;
}
void operator*=(const Rational& other) {
*this = *this * other;
}
void operator/=(const Rational& other) {
*this = *this / other;
}
};

Rational pow(Rational r, int N) {
if (N == 0)return Rational(1);
if (N % 2 == 1)return r * pow(r, N - 1);
Rational tmp = pow(r, N / 2);
return tmp * tmp;
}
Rational operator"" _r(unsigned long long val) {
return Rational(val);
}

/////////////////////

//KMP文字列検索
//計算量:O(|S|+|W|)
//ボイヤームーアは実務では良くても競プロでは使ってはいけない(最悪ケースで二乗オーダ)
struct KMP {
std::string W;	//検索する文字列
std::vector<int> T;	//テーブル
public:
//計算量:O(|W|)
KMP(const std::string& W_) :W(W_) {
T.resize(W.size() + 1);
int i = 2;		//T の中で現在計算している位置
int j = 0;		//現在見ているサブ文字列の次の文字のインデックス。0から始まる
//先頭ふたつの値は固定。ただしアルゴリズムの実装によっては具体的値は異なる
T[0] = -1;
if (2 <= W.size()) {
T[1] = 0;
}
while (i <= W.size()) {
if (W[i - 1] == W[j]) {
T[i] = j + 1;
i = i + 1;
j = j + 1;
}
else if (j > 0) {
j = T[j];
}
else {
T[i] = 0;
i = i + 1;
}
}
}
//return: W が見つかった際の S 内の位置を全列挙(先端が0番目)
//全列挙でも一個探す場合と計算量的に変わらない
//(むしろ一個探す実装を繰り返して全列挙するとTLEする)
//Sを変えて複数回呼べる
//計算量:O(|S|)
std::vector<int> searchAll(const std::string& S)const {
std::vector<int>res;
//S 内の現在照合中の開始位置
int m = 0;
//W 内の現在位置
int i = 0;
while (m + i < S.size()) {
if (W[i] == S[m + i]) {
++i;
if (i == W.size()) {
res.push_back(m);
}
else {
continue;
}
}
m = m + i - T[i];
if (i > 0) {
i = T[i];
}
}
return res;
}
};

//累積和
std::vector<int> MAKESUM(const std::vector<int>& A) {
std::vector<int>res(A.size() + 1);
res[0] = 0;
for (int i = 1; i < A.size() + 1; ++i) {
res[i] = res[i - 1] + A[i - 1];
}
return res;
}

//セグメント木
struct SegmentTree {
std::vector<int>val;
size_t size;
public:
SegmentTree(size_t sz) {
//2の累乗でないといけない
assert((sz & (sz - 1)) == 0);
//
val.resize(sz * 2 - 1);
size = sz;
}
void fill(int v) {
std::fill(val.begin(), val.end(), v);
}
//TODO 全部に初期値を入れてからやるばあいはまとめて更新するとO(N)でできる
//	setをN回呼ぶとNlogNかかる

//群の演算
static int operate(int a, int b) {
return a + b;
}
//群の単位元
static int unit() {
return 0;
}
void set(int idx, int v) {
assert(0 <= idx && idx < size);
int offset = size;
val[offset - 1 + idx] = v;
int segSize = 1;
while (offset > 1) {
val[offset / 2 - 1 + idx / segSize / 2]
= SegmentTree::operate(val[offset - 1 + idx / segSize / 2 * 2 + 0], val[offset - 1 + idx / segSize / 2 * 2 + 1]);
offset /= 2;
segSize *= 2;
}
}
int query(int a, int b, int k, int l, int r) {
// https://www.slideshare.net/iwiwi/ss-3578491 を参考にした
if (r <= a || b <= l) return unit();
// 交差しない？
if (a <= l && r <= b) return val[k];
// 完全に含む？
else {
int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return operate(vl, vr);
}

}
//[a,b)のoperateの結果を得る
//max,gcdなど逆演算ができないものを考慮すると[0,a)が取得できるだけでは不十分
int get(int a, int b) {
return query(a, b, 0, 0, size);
}
};

template <class T>
void MAX(T& val, T min) {
val = std::max({ val,min });
}

template <class T>
void MIN(T& val, T min) {
val = std::min({ val,min });
}

template <class T>
void PRINT(const T& con) {
cout << "(";
for (auto& one : con) {
cout << one << ",";
}
cout << ")" << endl;
}

constexpr double pi = 3.141592653589793238462;
//////////////////

for (int nnn = 0; nnn < N; ++nnn) { \
cin >> name[nnn]; \
}

for (int nnn = 0; nnn < N; ++nnn) { \
cin >> name0[nnn];cin >> name1[nnn]; \
}

for (int nnn = 0; nnn < N; ++nnn) { \
cin >> name0[nnn];cin >> name1[nnn];cin >> name2[nnn]; \
}

cin >> name;

void proc();

signed main() {
ios::sync_with_stdio(false);
cout << std::setprecision(20);
proc();
return 0;
}

/*
--------------------------------------------------------
--------------------------------------------------------
---------------    template      ----------------------
--------------------------------------------------------
--------------------------------------------------------
*/

#if 0

struct S {
int dis = -1;
};

template<class T>
void Graph<T>::dfsCustom(int pos, int prev) {
int nEdge = 0;
for (auto& e : vertex[pos].edges) {
const int next = e.next;
if (next == prev) continue;
if (val(next).dis == -1) {
val(next).dis = val(pos).dis + 1;
dfsCustom(next, pos);
++nEdge;
}
else if (val(next).dis < val(pos).dis) {
//ここに来たなら木ではない(後退辺の処理)
assert(false);
}
}
//
int rat = K - 1;
if (val(pos).dis == 0) {
for (int i = 0; i < nEdge; ++i) {
res *= rat;
modify(res);
--rat;
}
}
else {
--rat;
for (int i = 0; i < nEdge; ++i) {
res *= rat;
modify(res);
--rat;
}
}
}

#endif

void proc() {
//
std::multiset<int>set;
for (int i = 0; i < N; ++i) {
}
int res = 0;
for (int i = 1; i <= M; ++i) {
if (set.empty())continue;
auto itr = set.end();
--itr;
res += *itr;
set.erase(itr);
}

cout << res << endl;
}

#endif

#### Submission Info

Submission Time 2019-08-10 21:28:07+0900 D - Summer Vacation HNN_8127 C++14 (GCC 5.4.1) 0 13671 Byte WA 53 ms 14208 KB

#### Judge Result

Set Name All Sample
Score / Max Score 0 / 400 0 / 0
Status
 AC × 9 WA × 12
 AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 5 ms 6272 KB
sample_02 AC 5 ms 6272 KB
sample_03 AC 5 ms 6272 KB
testcase_01 AC 11 ms 7424 KB
testcase_02 AC 6 ms 6528 KB
testcase_03 WA 34 ms 12032 KB
testcase_04 WA 50 ms 13440 KB
testcase_05 WA 50 ms 13440 KB
testcase_06 AC 39 ms 13056 KB
testcase_07 WA 41 ms 14208 KB
testcase_08 WA 21 ms 9088 KB
testcase_09 WA 38 ms 11776 KB
testcase_10 WA 51 ms 13440 KB
testcase_11 WA 40 ms 11648 KB
testcase_12 WA 17 ms 8448 KB
testcase_13 WA 42 ms 11904 KB
testcase_14 AC 32 ms 10368 KB
testcase_15 AC 9 ms 7040 KB
testcase_16 AC 35 ms 10496 KB
testcase_17 WA 12 ms 7680 KB
testcase_18 WA 53 ms 13696 KB