oj.uz

Submission #243559

# Submission time Handle Problem Language Result Execution time Memory
243559 2020-07-01T10:15:41 Z abacaba Schools (IZhO13_school) C++14
60 / 100
 2000 ms 9312 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 inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 3e5 + 15;
const int M = 1e7;
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 = M;
    pii best(-1, -1);
    while(l1 <= r1) {
        int l2 = 0, r2 = M;
        int mid1 = l1 + r1 >> 1;
        int res2 = -1;
        while(l2 <= r2) {
            int mid2 = l2 + r2 >> 1;
            proceed(mid1, mid2);
            if(dp[n].y < y)
                r2 = mid2 - 1;
            else
                l2 = mid2 + 1, res2 = mid2;
        }
        proceed(mid1, res2);
        if(dp[n].x < x)
            r1 = mid1 - 1;
        else
            l1 = mid1 + 1, best = {mid1, res2};
    }
    assert(best.f != -1);
    assert(best.se != -1);
    proceed(best.f, best.se);
    cout << dp[n].val + 1ll * x * best.f + 1ll * y * best.se << endl;
    return 0;
}

Compilation message

school.cpp:100: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:113: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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 29 ms 512 KB Output is correct
8 Correct 33 ms 512 KB Output is correct
9 Correct 38 ms 432 KB Output is correct
10 Correct 38 ms 512 KB Output is correct
11 Correct 43 ms 512 KB Output is correct
12 Correct 43 ms 512 KB Output is correct
13 Correct 252 ms 1272 KB Output is correct
14 Incorrect 513 ms 2296 KB Output isn't correct
15 Incorrect 740 ms 4164 KB Output isn't correct
16 Runtime error 1391 ms 9312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Incorrect 1809 ms 5624 KB Output isn't correct
18 Incorrect 1682 ms 6140 KB Output isn't correct
19 Incorrect 1953 ms 6488 KB Output isn't correct
20 Execution timed out 2090 ms 7288 KB Time limit exceeded