QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197767 | #6962. Far Away from Home | PPP# | AC ✓ | 562ms | 43524kb | C++17 | 1.5kb | 2023-10-02 19:41:15 | 2023-10-02 19:41:15 |
Judging History
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define X first
#define Y second
const ll mod = 1000000007;
void solve()
{
ll n, C;
cin >> n >> C;
vector<ll> prv(C,mod*mod);
vector<pair<ll,ll>> Q;
for (ll i=0;i<n;i++)
{
ll x, k;
cin >> x >> k;
x *= 2;
for (ll j=0;j<k;j++)
{
ll w;
cin >> w;
w--;
Q.push_back({x,w});
}
}
sort(Q.begin(),Q.end());
vector<pair<ll,ll>> ord;
ll S = 0;
ll A = mod*mod;
for (ll i=0;i<Q.size();i++)
{
ll p = Q[i].Y, x = Q[i].X;
ord.push_back({x,2});
if (prv[p]==mod*mod)
{
S += x;
prv[p] = x;
continue;
}
ord.push_back({(x+prv[p])/2,-2});
prv[p] = x;
}
sort(ord.begin(),ord.end());
ll D = -C;
S = S-C*ord[0].X;
A = S;
for (ll i=0;i<ord.size();i++)
{
if (i>0)
{
ll del = ord[i].X-ord[i-1].X;
S += del*D;
A = min(A,S);
}
D += ord[i].Y;
}
cout << A/2 << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//#ifdef DEBUG
// freopen("input.txt", "r", stdin);
//#endif
ll T = 1;
cin >> T;
while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 562ms
memory: 43524kb
input:
5 99674 20 763240852 6 13 12 1 19 14 15 907986528 9 9 13 2 3 10 5 8 11 20 405330475 5 8 20 18 19 7 350664157 3 14 7 11 866108800 7 5 15 19 17 7 1 16 243752093 3 5 6 16 957293963 7 6 2 7 12 3 8 11 87866078 8 8 15 2 10 16 4 5 18 599501459 4 15 20 10 13 75898433 3 15 1 13 634860118 3 4 10 12 931882462 ...
output:
8461 225014484653807 4191726 32192409196439 2242332818199
result:
ok 5 lines