AtCoder Beginner Contest 441

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
signed main() {
25
    // ios::sync_with_stdio(0);
26
    // cin.tie(0);
27
    // cout.tie(0);
28
    int p, q, x, y;
29
    cin >> p >> q >> x >> y;
30
    if(p <= x && x <= p + 99 && q <= y && y <= q + 99) {
31
        puts("Yes");
32
    } else puts("No");
33
    return 0;
34
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
int n, m, q;
25
string S, T;
26
map<char, int> tk, ao;
27
signed main() {
28
    // ios::sync_with_stdio(0);
29
    // cin.tie(0);
30
    // cout.tie(0);
31
    cin >> n >> m >> S >> T;
32
    for(auto x : S) tk[x] = 1;
33
    for(auto x : T) ao[x] = 1;
34
    cin >> q;
35
    while(q--) {
36
        string s;
37
        cin >> s;
38
        int f1 = 1, f2 = 1;
39
        for(auto x : s) {
40
            f1 &= tk.count(x);
41
            f2 &= ao.count(x);
42
        }
43
        if(f1 ^ f2) {
44
            if(f1) cout << "Takahashi" << endl;
45
            else cout << "Aoki" << endl;
46
        } else cout << "Unknown" << endl;
47
    }
48
    return 0;
49
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 3e5 + 5;
25
int n, k;
26
ll X, a[N];
27
signed main() {
28
    ios::sync_with_stdio(0);
29
    cin.tie(0);
30
    cout.tie(0);
31
    cin >> n >> k >> X;
32
    for(int i = 1;i <= n;i++) cin >> a[i];
33
    sort(a + 1, a + n + 1);
34
    int ans = n - k + 1;
35
    ll res = 0;
36
    // for(int i = k;i <= n;i++) res += a[i];
37
    res = a[k];
38
    for(int i = k - 1;i >= 1;i--) {
39
        if(res < X) res += a[i], ans++;
40
        else break;
41
    }
42
    if(res >= X) cout << ans << endl;
43
    else cout << "-1" << endl;
44
    return 0;
45
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int n, m, L, S, T;
26
bool v[N];
27
unordered_map<int, bool> mp[12];
28
vector<PII > p[N];
29
struct node {
30
    int x, cnt, sum;
31
};
32
void bfs() {
33
    queue<node> q;
34
    q.push({1, 0, 0});
35
    while(q.size()) {
36
        node t = q.front();
37
        q.pop();
38
        int x = t.x, cnt = t.cnt, sum = t.sum;
39
        if(cnt == L) {
40
            if(S <= sum && sum <= T && !v[x]) {
41
                v[x] = 1;
42
            }
43
            continue;
44
        }
45
        for(auto [y, z] : p[x]) if(cnt + 1 <= L && sum + z <= T) {
46
            q.push({y, cnt + 1, sum + z});
47
        }
48
    }
49
}
50
signed main() {
51
    ios::sync_with_stdio(0);
52
    cin.tie(0);
53
    cout.tie(0);
54
    cin >> n >> m >> L >> S >> T;
55
    for(int i = 1;i <= m;i++) {
56
        int x, y, z;
57
        cin >> x >> y >> z;
58
        p[x].pb({y, z});
59
    }
60
    bfs();
61
    for(int x = 1;x <= n;x++) if(v[x]) cout << x << " ";
62
    cout << endl;
63
    return 0;
64
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 5e5 + 5;
25
int n, a[N], s[N];
26
string st;
27
struct BIT {
28
    int c[(N << 1) + 5];
29
    void add(int i, int d) {
30
        i += N;
31
        for(int x = i;x <= n + N;x += (x & -x)) {
32
            c[x] += d;
33
        }
34
    }
35
    int query(int i) {
36
        i += N;
37
        int res = 0;
38
        for(int x = i;x;x -= (x & -x)) {
39
            res += c[x];
40
        }
41
        return res;
42
    }
43
} T;
44
signed main() {
45
    // ios::sync_with_stdio(0);
46
    // cin.tie(0);
47
    // cout.tie(0);
48
    cin >> n >> st;
49
    st = " " + st;
50
    for(int i = 1;i <= n;i++) {
51
        if(st[i] == 'A') a[i] = 1;
52
        else if(st[i] == 'B') a[i] = -1;
53
        else if(st[i] == 'C') a[i] = 0;
54
        s[i] = s[i - 1] + a[i];
55
        // printf("s[%d]=%d\n", i, s[i]);
56
    }
57
    T.add(0, 1);
58
    ll ans = 0;
59
    for(int i = 1;i <= n;i++) {
60
        ans += T.query(s[i] - 1);
61
        T.add(s[i], 1);
62
    }
63
    cout << ans << endl;
64
    return 0;
65
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 1e3 + 5, M = 5e4 + 5;
25
int n, m, p[N], v[N];
26
ll ans = 0;
27
signed main() {
28
    ios::sync_with_stdio(0);
29
    cin.tie(0);
30
    cout.tie(0);
31
    cin >> n >> m;
32
    for(int i = 1;i <= n;i++) {
33
        cin >> p[i] >> v[i];
34
    }
35
    vector<ll> f(M, -1e9);
36
    f[0] = 0;
37
    for(int i = 1;i <= n;i++) {
38
        for(int j = m;j >= p[i];j--) f[j] = max(f[j], f[j - p[i]] + v[i]);
39
    }
40
    for(int i = 0;i <= m;i++) ans = max(ans, f[i]);
41
    vector<ll> pre(M, -1e9);
42
    vector<vector<ll> > suf(N);
43
    pre[0] = 0;
44
    suf[n + 1].resize(m + 5);
45
    for(int i = 1;i <= m;i++) suf[n + 1][i] = 0;
46
    suf[n + 1][0] = 0;
47
    for(int i = n;i >= 1;i--) {
48
        suf[i] = suf[i + 1];
49
        for(int j = m;j >= p[i];j--) suf[i][j] = max(suf[i][j], suf[i][j - p[i]] + v[i]);
50
        for(int j = 1;j <= m;j++) suf[i][j] = max(suf[i][j], suf[i][j - 1]);
51
    }
52
    for(int i = 1;i <= n;i++) {
53
        ll res = 0;
54
        for(int j = 0;j <= m;j++) res = max(res, pre[j] + suf[i + 1][m - j]);
55
        ll tres = 0;
56
        for(int j = 0;j <= m - p[i];j++) tres = max(tres, pre[j] + suf[i + 1][m - p[i] - j] + v[i]);
57

58

59
        for(int j = m;j >= p[i];j--) pre[j] = max(pre[j], pre[j - p[i]] + v[i]);
60
        for(int j = 1;j <= m;j++) pre[j] = max(pre[j], pre[j - 1]);
61
        if(res == ans) {
62
            if(tres == ans) putchar('B');
63
            else putchar('C');
64
        }
65
        else if(res < ans) putchar('A');
66
    }
67
    return 0;
68
}