Click to show code.
using namespace std;
using ll = long long;
const int NMAX = 2e5 + 11;
int a[NMAX];
int main(void)
{
int n;
ll ans = 0;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < n; ++i)
{
ans += max(0, a[i - 1] - a[i]);
a[i] = max(a[i - 1], a[i]);
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll MOD = 1e9 + 7;
ll solve(ll n)
{
ll target;
target = (n * (n + 1)) / 2;
if (target % 2 != 0)
return 0;
target /= 2;
vvll dp(n + 1, vll(target + 1, 0));
dp[0][0] = 1;
for (ll x = 1; x <= n; ++x)
{
for (ll sum = 1; sum <= target; ++sum)
{
ll &ans = dp[x][sum];
ans = dp[x - 1][sum];
if (sum - x >= 0)
ans = (ans + dp[x - 1][sum - x] % MOD) % MOD;
}
}
return dp[n][target];
}
int main(void)
{
ll n;
cin >> n;
cout << solve(n) << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
const int NMAX = 1e6 + 11;
bool taken[NMAX];
int ntaken;
bool possible(int n, ll sum)
{
if (sum % 2 == 1)
return false;
sum /= 2;
for (int i = n; i >= 1 and sum > 0; --i)
{
if (sum - i >= 0)
{
++ntaken;
taken[i] = true;
sum -= i;
}
}
return true;
}
int main(void)
{
int n;
ll sum = 0;
cin >> n;
for (int i = 1; i <= n; ++i)
sum += i;
if (possible(n, sum))
{
cout << "YES" << endl;
cout << ntaken << endl;
for (int i = 1; i <= n; ++i)
if (taken[i])
cout << i << " ";
cout << endl;
cout << n - ntaken << endl;
for (int i = 1; i <= n; ++i)
if (not taken[i])
cout << i << " ";
}
else
cout << "NO" << endl;
return 0;
}
Click to show code.
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
int main(void)
{
int n, m;
cin >> n >> m;
set<ii> h;
for (int i = 0; i < n; ++i)
{
int hi;
cin >> hi;
h.emplace(hi, i);
}
for (int i = 0; i < m; ++i)
{
int ti;
cin >> ti;
auto it = h.upper_bound({ti, 1e9});
if (it != h.begin())
{
--it;
cout << it->first << endl;
h.erase(it);
}
else
cout << -1 << endl;
}
return 0;
}
Click to show code.
using namespace std;
using vi = vector<int>;
int main(void)
{
int n, x, l = 0, ans = 0;
cin >> n >> x;
vi p(n);
for (auto &pi : p)
cin >> pi;
sort(p.begin(), p.end());
for (int i = n - 1; i >= l; --i)
{
if (p[i] + p[l] <= x)
++l;
++ans;
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 1e5 + 11;
int n, s, deg[NMAX];
vi g[NMAX];
void dfs(int u, int p)
{
deg[u] = 0;
for (auto v : g[u])
{
deg[u]++;
if (v != p)
dfs(v, u);
}
}
int main(void)
{
cin >> n >> s;
for (int i = 0; i < n - 1; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
int l = count_if(deg + 1, deg + n + 1, [](int d) { return d == 1; });
cout << fixed << setprecision(12) << (2.0 * s) / (1.0 * l) << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using predicate = function<bool(ll)>;
const int NMAX = 2e5 + 11;
ll n, k, x[NMAX];
ll bs(ll l, ll r, predicate p)
{
while (l < r)
{
ll m = l + (r - l) / 2;
if (p(m))
r = m;
else
l = m + 1;
}
return l;
}
bool max_sum_test(ll max_sum)
{
ll last_sum = 0;
int n_partitions = 0;
for (int i = 0; i < n; ++i)
{
if (last_sum + x[i] > max_sum)
{
last_sum = 0;
n_partitions += 1;
}
last_sum += x[i];
}
n_partitions += 1;
return (n_partitions <= k);
}
int main(void)
{
cin >> n >> k;
for (int i = 0; i < n; ++i)
cin >> x[i];
cout << bs(*max_element(x, x + n), 1e18, max_sum_test) << endl;
return 0;
}
Click to show code.
using namespace std;
using vi = vector<int>;
int main(void)
{
int n, m, k, ix, ans;
cin >> n >> m >> k;
vi a(n), b(m);
for (auto &ai : a)
cin >> ai;
for (auto &bi : b)
cin >> bi;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
ix = 0, ans = 0;
for (auto bi : b)
{
while (ix < n and a[ix] < bi - k)
++ix;
if (bi - k <= a[ix] and a[ix] <= bi + k)
++ix, ++ans;
if (ix >= n)
break;
}
cout << ans << endl;
return 0;
}
Click to show code.
using namespace std;
int main(void)
{
int n, x;
cin >> n;
vector<bool> is_present(n + 1, false);
for (int i = 0; i < n - 1; ++i)
{
cin >> x;
is_present[x] = true;
}
for (int i = 1; i <= n; ++i)
if (not is_present[i])
cout << i << endl;
return 0;
}
Click to show code.
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
copy(first, last, ostream_iterator<T>(cout, delim));
}
template <long long M, typename T = long long>
class NumMod
{
static_assert(std::is_integral<T>::value, "Integral required.");
T x;
public:
NumMod<M, T>(T x) : x(x) {}
NumMod<M, T>(NumMod<M, T> &n) : x(n.x) {}
explicit operator T() const { return x; }
T v(void) const { return (this->x + M) % M; }
NumMod<M, T> &operator=(NumMod<M, T> const &y)
{
this->x = y.v();
return *this;
}
NumMod<M, T> &operator=(T const &y)
{
return this->operator=(NumMod<M, T>(y));
}
NumMod<M, T> operator+(NumMod<M, T> const &y) { return (v() + y.v()) % M; }
NumMod<M, T> operator+(T const &y)
{
return this->operator+(NumMod<M, T>(y));
}
NumMod<M, T> operator-(NumMod<M, T> const &y) { return (v() - y.v()) % M; }
NumMod<M, T> operator-(T const &y)
{
return this->operator-(NumMod<M, T>(y));
}
NumMod<M, T> &operator+=(const NumMod<M, T> &y)
{
return this->operator=(operator+(y));
}
NumMod<M, T> operator*(NumMod<M, T> y) { return (v() * y.v()) % M; }
NumMod<M, T> operator*(T y) { return this->operator*(NumMod<M, T>(y)); }
};
ll const MOD = 1e9 + 7;
NumMod<MOD> sum(NumMod<MOD> n) { return n * (n + 1) * ((MOD + 1) / 2); }
int main(void)
{
ios::sync_with_stdio(false), cin.tie(NULL);
ll n;
cin >> n;
NumMod<MOD> ans(0);
for (ll i = 1; i <= n; ++i)
{
ll times = n / i, r = n / times;
ans += NumMod<MOD>(times) * (sum(r) - sum(i - 1));
i = r;
}
cout << ll(ans) << endl;
return 0;
}