QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#345377 | #3418. Highway of the Future | PetroTarnavskyi# | WA | 808ms | 11596kb | C++20 | 2.1kb | 2024-03-06 21:09:37 | 2024-03-06 21:09:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int MX = 1 << 20;
const int X = 101;
const int Y = 10047;
int n;
int cnt[MX];
VI vecs[X];
vector<PII> vecPairs[X];
int g[MX];
void precalc()
{
FOR(i, 1, X)
FOR(j, 0, Y)
{
int gc = gcd(i, j);
g[Y * i + j] = (Y * i + j) / gc;
}
}
void solve()
{
FOR(i, 0, X)
{
vecs[i].clear();
vecPairs[i].clear();
}
FOR(i, 0, n)
{
int t, v;
cin >> t >> v;
vecs[v].PB(v * t);
}
int ans = 0;
FOR(k, 1, X)
{
sort(ALL(vecs[k]));
for (int j = 0; j < SZ(vecs[k]); )
{
int l = j;
while (l < SZ(vecs[k]) && vecs[k][l] == vecs[k][j])
{
l++;
}
ans = max(ans, l - j);
vecPairs[k].PB({vecs[k][j], l - j});
j = l;
}
}
int used = 0;
const int MAGIC = max(1000, (int)(0.14 * n));
FOR(x1, 1, X)
{
for (auto [y1, c] : vecPairs[x1])
{
used++;
if (used > MAGIC)
break;
int cur = 0;
FOR(x2, x1 + 1, X)
{
auto le = lower_bound(ALL(vecPairs[x2]), MP(y1, 0)),
ri = lower_bound(ALL(vecPairs[x2]), MP(y1 + (x2 - x1) * 100 + 1, 0));
int dx = x2 - x1;
int dx2 = Y * dx - y1;
for (auto it = le; it != ri; it++)
{
int& res = cnt[g[dx2 + it->F]];
res += it->S;
cur = max(cur, res);
}
}
FOR(x2, x1 + 1, X)
{
auto le = lower_bound(ALL(vecPairs[x2]), MP(y1, 0)),
ri = lower_bound(ALL(vecPairs[x2]), MP(y1 + (x2 - x1) * 100 + 1, 0));
int dx = x2 - x1;
int dx2 = Y * dx - y1;
for (auto it = le; it != ri; it++)
{
cnt[g[dx2 + it->F]] -= it->S;
}
}
ans = max(ans, cur + c);
}
}
cout << ans << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
precalc();
while (cin >> n)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 23ms
memory: 7892kb
input:
4 10 10 10 10 15 20 15 20 3 100 100 100 1 100 1
output:
4 3
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 808ms
memory: 11596kb
input:
4384 887 78 916 94 336 87 493 50 422 63 28 91 60 64 927 41 427 73 737 12 369 68 430 83 531 63 124 68 136 30 803 23 59 70 168 94 457 12 43 30 374 22 920 85 538 99 325 16 371 14 527 92 981 57 874 63 171 97 282 6 926 85 328 37 506 47 730 14 858 25 896 83 546 15 368 35 365 44 751 88 809 77 179 89 585 4 ...
output:
9 33 37 32 12 10 25 24 30 44 46 29 43 37 11 17 24 40 24 45 27 42 34 21 34
result:
wrong answer 1st lines differ - expected: '14', found: '9'