oj.uz

Submission #243546

# Submission time Handle Problem Language Result Execution time Memory
243546 2020-07-01T10:00:49 Z abacaba Schools (IZhO13_school) C++14
20 / 100
 2000 ms 7292 KB 
#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;
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) {
    for(int i = 0; i <= n; ++i)
        dp[i].val = dp[i].x = dp[i].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 = N;
    pii best(-1, -1);
    while(l1 <= r1) {
        int l2 = 0, r2 = N;
        int mid1 = l1 + r1 >> 1;
        int res2 = -1;
        while(l2 <= r2) {
            int mid2 = r2 + 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 << (ll)(dp[n].val + x * best.f + y * best.se) << endl;
    return 0;
}

Compilation message

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:109:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid1 = l1 + r1 >> 1;
                    ~~~^~~~
school.cpp:112:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int mid2 = r2 + r2 >> 1;
                        ~~~^~~~
school.cpp: In function 'void proceed(int, int)':
school.cpp:73: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:73: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:73: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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 504 KB Output is correct
2 Correct 223 ms 504 KB Output is correct
3 Correct 160 ms 504 KB Output is correct
4 Execution timed out 2084 ms 384 KB Time limit exceeded
5 Correct 1819 ms 504 KB Output is correct
6 Execution timed out 2097 ms 384 KB Time limit exceeded
7 Execution timed out 2087 ms 384 KB Time limit exceeded
8 Execution timed out 2095 ms 512 KB Time limit exceeded
9 Execution timed out 2098 ms 512 KB Time limit exceeded
10 Execution timed out 2096 ms 512 KB Time limit exceeded
11 Execution timed out 2094 ms 512 KB Time limit exceeded
12 Execution timed out 2067 ms 512 KB Time limit exceeded
13 Execution timed out 2089 ms 1152 KB Time limit exceeded
14 Execution timed out 2091 ms 2176 KB Time limit exceeded
15 Execution timed out 2090 ms 4092 KB Time limit exceeded
16 Execution timed out 2097 ms 4608 KB Time limit exceeded
17 Execution timed out 2093 ms 5496 KB Time limit exceeded
18 Execution timed out 2096 ms 6012 KB Time limit exceeded
19 Execution timed out 2088 ms 6392 KB Time limit exceeded
20 Execution timed out 2095 ms 7292 KB Time limit exceeded