1132A - Regular Bracket Sequence
Tutorial
Tutorial is loading...
Solution (BledDest)
cnt = []
for i in range(4):
cnt.append(int(input()))
if(cnt[0] == cnt[3] and (cnt[2] == 0 or cnt[0] > 0)):
print(1)
else:
print(0)
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 300009;
int n;
int a[N];
long long res[N];
int main() {
long long sum = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
sum += a[i];
}
sort(a, a + n);
memset(res, -1, sizeof res);
int m;
scanf("%d", &m);
for(int i = 0; i < m; ++i){
int c;
scanf("%d", &c);
if(res[c] == -1){
res[c] = sum - a[n - c];
}
printf("%lld\n", res[c]);
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 5043;
int p1[N];
int p2[N];
int p3[N];
int n, q;
int l[N], r[N];
int solve(int idx)
{
memset(p1, 0, sizeof p1);
for(int i = 0; i < q; i++)
{
if(i == idx) continue;
p1[l[i]]++;
p1[r[i]]--;
}
memset(p2, 0, sizeof p2);
int c = 0;
for(int i = 0; i < n; i++)
{
c += p1[i];
p2[i] = c;
}
memset(p3, 0, sizeof p3);
for(int i = 0; i < n; i++)
p3[i + 1] = p3[i] + (p2[i] == 1 ? 1 : 0);
int ans = -int(1e9);
for(int i = 0; i < q; i++)
{
if(i == idx) continue;
ans = max(ans, p3[l[i]] - p3[r[i]]);
}
for(int i = 0; i < n; i++)
if(p2[i] > 0)
ans++;
return ans;
}
int main()
{
cin >> n >> q;
for(int i = 0; i < q; i++)
{
cin >> l[i] >> r[i];
l[i]--;
}
int ans = 0;
for(int i = 0; i < q; i++)
ans = max(ans, solve(i));
cout << ans << endl;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
const long long INF64 = 1e18;
int n, k;
long long a[N];
int b[N];
long long cur[N];
vector<int> qr[N];
bool check(long long x){
forn(i, k) qr[i].clear();
forn(i, n) cur[i] = a[i];
forn(i, n){
long long t = cur[i] / b[i] + 1;
cur[i] %= b[i];
if (t < k) qr[t].push_back(i);
}
int lst = 0;
forn(t, k){
while (lst < k && qr[lst].empty())
++lst;
if (lst <= t)
return false;
if (lst == k)
return true;
int i = qr[lst].back();
if (cur[i] + x < b[i]){
cur[i] += x;
continue;
}
qr[lst].pop_back();
long long nt = (cur[i] + x) / b[i];
cur[i] = (cur[i] + x) % b[i];
if (lst + nt < k)
qr[lst + nt].push_back(i);
}
return true;
}
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%lld", &a[i]);
forn(i, n) scanf("%d", &b[i]);
long long l = 0, r = INF64;
while (l < r - 1){
long long m = (l + r) / 2;
if (check(m))
r = m;
else
l = m;
}
if (!check(r))
puts("-1");
else
printf("%lld\n", check(l) ? l : r);
return 0;
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
const int L = 840;
typedef long long li;
li dp[N][L * N];
li W;
li cnt[N];
int main()
{
cin >> W;
for(int i = 0; i < 8; i++)
cin >> cnt[i];
for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
dp[0][0] = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < L * N; j++)
{
if(dp[i][j] == -1) continue;
int b = L / (i + 1);
if(cnt[i] < b)
b = cnt[i];
for(int k = 0; k <= b; k++)
{
li& d = dp[i + 1][j + k * (i + 1)];
d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
}
}
}
li ans = 0;
for(int j = 0; j < L * N; j++)
{
if(j > W || dp[8][j] == -1)
continue;
ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
}
cout << ans << endl;
}
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n;
string s;
int dp[N][N];
int calc(int l, int r){
int &res = dp[l][r];
if(res != -1) return res;
if(l > r) return res = 0;
if(l == r) return res = 1;
res = 1 + calc(l + 1, r);
for(int i = l + 1; i <= r; ++ i)
if(s[l] == s[i])
res = min(res, calc(l + 1, i - 1) + calc(i, r));
return res;
}
int main(){
cin >> n >> s;
memset(dp, -1, sizeof dp);
cout << calc(0, n - 1);
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
int n, k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.assign(n, 0);
fore(i, 0, n)
cin >> a[i];
return true;
}
int T = 0;
vector< vector<int> > g;
vector<int> tin, tout;
void dfs(int v) {
tin[v] = T++;
for(int to : g[v])
dfs(to);
tout[v] = T;
}
vector<int> Tmax, Tadd;
inline void push(int v) {
Tadd[2 * v + 1] += Tadd[v];
Tadd[2 * v + 2] += Tadd[v];
Tadd[v] = 0;
}
inline int getmax(int v) {
return Tmax[v] + Tadd[v];
}
void addVal(int v, int l, int r, int lf, int rg, int val) {
if(l == lf && r == rg) {
Tadd[v] += val;
return;
}
int mid = (l + r) >> 1;
push(v);
if(lf < mid) addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
if(rg > mid) addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
}
inline void solve() {
g.resize(n + 1);
tin.resize(n + 1, 0);
tout.resize(n + 1, 0);
vector<int> st;
for(int i = n - 1; i >= 0; i--) {
while(!st.empty() && a[st.back()] <= a[i])
st.pop_back();
int nxt = st.empty() ? n : st.back();
g[nxt].push_back(i);
st.push_back(i);
}
dfs(n);
Tmax.assign(4 * (n + 1), 0);
Tadd.assign(4 * (n + 1), 0);
fore(i, 0, k - 1)
addVal(0, 0, n + 1, tin[i], tout[i], +1);
for(int l = 0; l + k <= n; l++) {
addVal(0, 0, n + 1, tin[l + k - 1], tout[l + k - 1], +1);
cout << getmax(0) << " ";
addVal(0, 0, n + 1, tin[l], tout[l], -1);
}
cout << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}