| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 243566 |
2020-07-01T10:23:38 Z |
abacaba |
Schools (IZhO13_school) |
C++14 |
|
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;
^
| # |
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 |
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 |
