답안 #243566

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243566 2020-07-01T10:23:38 Z abacaba 학교 설립 (IZhO13_school) C++14
60 / 100
2000 ms 7288 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;
const int M = 1e5 + 1;
int n, x, y;
pii a[N];
 
struct pt {
    double 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(double c1, double 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;
    double l1 = 0, r1 = M;
    // pii best(-1, -1);
    pair <double, double> best(-1, -1);
    for(int iter1 = 0; iter1 < 30; ++iter1) {
    // while(l1 <= r1) {
        // int l2 = 0, r2 = M;
        double l2 = 0, r2 = M;
        double mid1 = (l1 + r1) / 2;
        double res2 = -1;
        for(int iter2 = 0; iter2 < 30; ++iter2) {
        // while(l2 <= r2) {
            double mid2 = (l2 + r2) / 2;
            proceed(mid1, mid2);
            if(dp[n].y > y)
                l2 = mid2;
            else
                r2 = mid2, res2 = mid2;
        }
        proceed(mid1, res2);
        if(dp[n].x > x)
            l1 = mid1;
        else
            r1 = mid1, best = {mid1, res2};
    }
    proceed(best.f, best.se);
    cout << (ll)(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 'void proceed(double, double)':
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;
                                ^
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 74 ms 512 KB Output is correct
8 Correct 74 ms 512 KB Output is correct
9 Incorrect 77 ms 512 KB Output isn't correct
10 Correct 85 ms 512 KB Output is correct
11 Correct 89 ms 512 KB Output is correct
12 Correct 87 ms 512 KB Output is correct
13 Correct 578 ms 1272 KB Output is correct
14 Incorrect 1429 ms 2232 KB Output isn't correct
15 Execution timed out 2087 ms 4088 KB Time limit exceeded
16 Execution timed out 2090 ms 4604 KB Time limit exceeded
17 Execution timed out 2091 ms 5496 KB Time limit exceeded
18 Execution timed out 2087 ms 6008 KB Time limit exceeded
19 Execution timed out 2091 ms 6392 KB Time limit exceeded
20 Execution timed out 2076 ms 7288 KB Time limit exceeded