Submission #243570

#	Time	Username	Problem	Language	Result	Execution time	Memory
243570		abacaba	Schools (IZhO13_school)	C++14	80 / 100	2080 ms	7416 KiB

school

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
inline void setin(string s) {
    freopen(s.c_str(), "r", stdin);
}
 
inline void setout(string s) {
    freopen(s.c_str(), "w", stdout);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}
 
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 3e5 + 15;
const int M = inf;
int n, x, y;
pii a[N];
 
struct pt {
    ll val;
    int x, y;
    bool operator < (const pt &rhs) const {
        if(val == rhs.val) {
            if(x == rhs.x)
                return y > rhs.y;
            return x > rhs.x;
        }
        return val < rhs.val;
    }
    bool operator > (const pt &rhs) const {
        if(val == rhs.val) {
            if(x == rhs.x)
                return y < rhs.y;
            return x < rhs.x;
        }
        return val > rhs.val;
    }
} dp[N];
 
inline void proceed(int c1, int c2) {
    dp[0].val = dp[0].x = dp[0].y = 0;
    for(int i = 1; i <= n; ++i) {
        dp[i] = dp[i-1];
        pt nw1 = {dp[i-1].val + a[i].f - c1, dp[i-1].x + 1, dp[i-1].y};
        pt nw2 = {dp[i-1].val + a[i].se - c2, dp[i-1].x, dp[i-1].y + 1};
        Max(dp[i], max(nw1, nw2));
    }
}
 
main() {
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    // setin("input.txt");
    cin >> n >> x >> y;
    for(int i = 1; i <= n; ++i)
        cin >> a[i].f >> a[i].se;
    int l1 = 0, r1 = M;
    pii best(-1, -1);
    // for(int iter1 = 0; iter1 < 20; ++iter1) {
    while(l1 <= r1) {
        int l2 = 0, r2 = M;
        int mid1 = l1 + r1 >> 1;
        int res2 = -1;
        // for(int iter2 = 0; iter2 < 20; ++iter2) {
        while(l2 <= r2) {
            int mid2 = l2 + r2 >> 1;
            proceed(mid1, mid2);
            if(dp[n].y > y)
                l2 = mid2 + 1;
            else
                r2 = mid2 - 1, res2 = mid2;
        }
        proceed(mid1, res2);
        if(dp[n].x > x)
            l1 = mid1 + 1;
        else
            r1 = mid1 - 1, best = {mid1, res2};
    }
    proceed(best.f, best.se);
    cout << dp[n].val + 1ll * x * best.f + 1ll * y * best.se << endl;
    return 0;
}

Compilation message (stderr)

school.cpp:99:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
school.cpp: In function 'int main()':
school.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid1 = l1 + r1 >> 1;
                    ~~~^~~~
school.cpp:114:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid2 = l2 + r2 >> 1;
                        ~~~^~~~
school.cpp: In function 'void proceed(int, int)':
school.cpp:74:32: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
                 return y > rhs.y;
                                ^
school.cpp: In function 'int main()':
school.cpp:74:32: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
                 return y > rhs.y;
                                ^
school.cpp:74:32: warning: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Wstrict-overflow]
                 return y > rhs.y;
                                ^

• Subtask 1: 80 / 100