QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197767#6962. Far Away from HomePPP#AC ✓562ms43524kbC++171.5kb2023-10-02 19:41:152023-10-02 19:41:15

Judging History

你现在查看的是最新测评结果

  • [2023-10-02 19:41:15]
  • 评测
  • 测评结果:AC
  • 用时:562ms
  • 内存:43524kb
  • [2023-10-02 19:41:15]
  • 提交

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;
}

详细

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