#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 = 1e3 + 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 = 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 = 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: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 = r2 + 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;
^
| # |
결과 |
실행 시간 |
메모리 |
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 |
10 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 6 |
Incorrect |
27 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 8 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 9 |
Incorrect |
8 ms |
512 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 11 |
Incorrect |
705 ms |
632 KB |
Output isn't correct |
| 12 |
Incorrect |
716 ms |
608 KB |
Output isn't correct |
| 13 |
Incorrect |
21 ms |
1152 KB |
Output isn't correct |
| 14 |
Incorrect |
43 ms |
2176 KB |
Output isn't correct |
| 15 |
Incorrect |
82 ms |
4088 KB |
Output isn't correct |
| 16 |
Execution timed out |
2089 ms |
4600 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2087 ms |
5500 KB |
Time limit exceeded |
| 18 |
Incorrect |
1506 ms |
6136 KB |
Output isn't correct |
| 19 |
Execution timed out |
2082 ms |
6392 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2089 ms |
7416 KB |
Time limit exceeded |
