Codeforces 1271 #Codeforces

1271A.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;

void solve() {
    ll ans = 0;
    ll val[6], tval[6];
    F(i, 6) cin >> val[i], tval[i] = val[i];
    ll a = min(val[0], val[3]), b;
    val[3] -= a;
    b = min(val[1], min(val[2], val[3]));
    ans = val[4] * a + val[5] * b;

    b = min(tval[1], min(tval[2], tval[3]));
    tval[3] -= b;
    a = min(tval[0], tval[3]);
    ans = max(ans, val[4] * a + val[5] * b);
    cout << ans << '\n';
}

signed main() {
    Android;
    solve();
}

1271D.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 5000 + 100;
vector<int> edge[maxn];
int to[maxn], req[maxn], hire[maxn], value[maxn], cum_req[maxn]={0};
int n, m, k;
int dp[maxn][maxn];

void maximize(int & ori, int new_val){
    if(ori < new_val) ori = new_val;
}

void solve() {
    memset(dp, -1, sizeof dp);
    int u, v;
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        to[i] = i;
        cin >> req[i] >> hire[i] >> value[i];
    }
    F(i, m){
        cin >> u >> v;
        to[v] = max(to[v], u);
    }
    for(int i=1; i<=n; i++)
        edge[to[i]].push_back(i);
    for(int i=1; i<=n; i++)
        sort(edge[i].begin(), edge[i].end(), [](int a, int b){return value[a] > value[b];});
    for(int i=n; i>0; i--)
        cum_req[i] = max(cum_req[i+1] - hire[i], req[i]);
    dp[0][k] = 0;
    for(int i=1; i<=n; i++){
        for(int j=cum_req[i]; j<=5000; j++){
            if(dp[i-1][j] == -1) continue;
            int cur = j + hire[i];
            dp[i][cur] = dp[i-1][j];
            for(int p=0; p<edge[i].size() && cur > p; p++)
                maximize(dp[i][cur - p - 1], dp[i][cur - p] + value[edge[i][p]]);
        }
    }
    int ans = -1;
    for(int i=0; i<=5000; i++) maximize(ans, dp[n][i]);
    cout << ans << '\n';
}

signed main() {
    Android;
    solve();
}

1271E.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)
 
using namespace std;
 
void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }
 
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;
ll n, k;
 
ll count_odd(ll x){
    ll ans = 0;
    ll p = 1;
    while(x * p <= n){
        if(x * p + p - 1 <= n){
            ans += p;
        }else{
            ans += n - p * x + 1;
            break;
        }
        p *= 2;
    }   
    return ans;
}
 
ll count_even(ll x){
    if(x == n) return 1;
    ll ans = 0;
    ll p = 1;
    while(x * p <= n){
        if(p * x + 2 * p - 1 <= n){
            ans += 2 * p;
        }else{
            ans += n - x * p + 1;
            break;
        }
        p *= 2;
    }
    return ans;
}
 
ll bin_search_odd(){
    ll l = 1, r = n, m;
    if(!(n&1)) r--;
    while(l < r){
        m = (l + r) >> 1;
        if(!(m&1)) m++;
        if(count_odd(m) < k)
            r = m - 2;
        else
            l = m;
    }
    return l;
}
 
ll bin_search_even(){
    ll l = 0, r = n, m;
    if(n & 1) r--;
    while(l < r){
        m = (l + r) >> 1;
        if(m & 1) m++;
        if(count_even(m) < k){
            r = m - 2;
        }else{
            l = m;
        }
    }
    return l;
}
 
void solve() {
    cin >> n >> k;
    cout << max(bin_search_even(), bin_search_odd()) << endl;
}
 
signed main() {
    Android;
    solve();
}

1271F.cpp

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

void redirect_input() { freopen("./input.txt", "r", stdin); }
void redirect_output() { freopen("./output.txt", "w", stdout); }

const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 100;
int a[2], b[2], c[2];
int d[7], ans[7], temp[7], counter[7];

int math(int * arr){return arr[0] + arr[1] + arr[2] + arr[3];}
int programing(int * arr){return arr[0] + arr[1] + arr[4] + arr[5];}
int pe(int * arr){return arr[0] + arr[2] + arr[4] + arr[6];}

bool dfs(int k){
    F(i, 7) temp[i] = i<k?ans[i]:0;
    F(i, 7) counter[i] = i<k?(d[i] - ans[i]):0;
    if(a[0] < math(temp) || b[0] < programing(temp) || c[0] < pe(temp)) return false;
    if(a[1] < math(counter) || b[1] < programing(counter) || c[1] < pe(counter)) return false;
    if(k == 7){
        F(i, 7) cout << ans[i] << ' ';
        cout << '\n';
        return true;
    }
    for(int i=0; i<=d[k]; i++){
        ans[k] = i;
        if(dfs(k + 1)) return true;
    }
    return false;
}

void solve() {
    F(i, 2) cin >> a[i] >> b[i] >> c[i];
    F(i, 7) cin >> d[i];
    if(a[0] + a[1] < math(d) || b[0] + b[1] < programing(d) || c[0] + c[1] < pe(d)){
           cout << "-1\n";
           return;
    } 
    if(!dfs(0)) cout << "-1\n";

}

signed main() {
    Android;
    int t;
    cin >> t;
    while(t--)
        solve();
}

1272B.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

const int maxn = 200 + 100;
char buffer[maxn];


void solve() {
    int n, b = 0, w = 0;
    cin >> n >> buffer;
    F(i, n){
        if (buffer[i] == 'B') b++;
        if (buffer[i] == 'W') w++;
    }
    if((b & 1) && (w & 1)){
        cout << -1 << '\n';
        return;
    }
    vector<int> ans;
    char swp = (w&1)?'B':'W', opp =  (w&1)?'W':'B';
    for(int i=n-1; i>0; i--){
        if(buffer[i] == swp){
            if(buffer[i-1] == swp){
                buffer[i-1] = opp;
                buffer[i] = opp;
            }else{
                buffer[i-1] = swp;
                buffer[i] = opp;
            }
            ans.push_back(i-1);
        }
    }
    cout << ans.size() << '\n';
    for(int i:ans) cout << i + 1 << ' ';
    if(ans.size() != 0) cout << '\n';

}

signed main() {
    Android;
    solve();
}

1272C.cpp

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define F(i, n) for(int i=0, _iter_max=n; i<_iter_max; i++)

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 200 + 100;
char buffer[maxn];


void solve() {
    ll top = 0, right = 0, beneath = 0, left = 0;
    ll n, x, y, r, c;
    cin >> n >> x >> y;
    F(i, n){
        cin >> r >> c;
        if (c > y) top++;
        if (c < y) beneath++;
        if (r > x) right++;
        if (r < x) left++;
    }

    ll mx = max(max(top, beneath), max(right, left));
    cout << mx << '\n';
    if(mx == top){
        cout << x << " " << y + 1 << '\n';
    }else if(mx == beneath){
        cout << x << " " << y - 1 << '\n';
    }else if(mx == left){
        cout << x - 1 << " " << y << '\n';
    }else if(mx == right){
        cout << x + 1 << " " << y << '\n';
    }
    
}

signed main() {
    Android;
    solve();
}