| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243545 |
2020-07-01T09:59:01 Z |
abacaba |
Schools (IZhO13_school) |
C++14 |
|
2000 ms |
12408 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 {
ld 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(ld c1, ld 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;
ld l1 = 0, r1 = N;
pair <ld, ld> best(-1, -1);
for(int iter1 = 0; iter1 < 20; ++iter1) {
// while(l1 <= r1) {
ld l2 = 0, r2 = N;
ld mid1 = (l1 + r1) / 2;
// int mid1 = l1 + r1 >> 1;
ld res2 = -1;
for(int iter2 = 0; iter2 < 20; ++iter2) {
ld mid2 = (l2 + r2) / 2;
// int mid2 = r2 + r2 >> 1;
proceed(mid1, mid2);
if(dp[n].y > y)
l2 = mid2;
else {
// cout << "asdsad" << endl;
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 << (int)(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 'void proceed(long double, long double)':
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;
^
| # |
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 |
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 |
75 ms |
640 KB |
Output is correct |
| 8 |
Correct |
74 ms |
640 KB |
Output is correct |
| 9 |
Correct |
76 ms |
640 KB |
Output is correct |
| 10 |
Correct |
79 ms |
760 KB |
Output is correct |
| 11 |
Correct |
84 ms |
640 KB |
Output is correct |
| 12 |
Correct |
86 ms |
640 KB |
Output is correct |
| 13 |
Correct |
551 ms |
2296 KB |
Output is correct |
| 14 |
Correct |
1245 ms |
3840 KB |
Output is correct |
| 15 |
Execution timed out |
2072 ms |
6904 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2074 ms |
7800 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2092 ms |
9336 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2085 ms |
10104 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2090 ms |
10872 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2090 ms |
12408 KB |
Time limit exceeded |
