CQUPT OJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#25956 #1053. youngmagician爱玩四个铁心脏2 Accepted 100 4454 ms 31736 K C++ 17 / 1.4 K dream_square 2025-03-14 11:39:57
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
#define int long long

#define maxn 1200000

#define endl '\n'


struct Node {
    int x, r, w;
};

int n, prefix[maxn];

bool cmp(Node n1, Node n2) { return n1.x < n2.x; }

int check(int x, vector<Node>& a) {
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid].x >= x) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return l;
}

void solve() {
    cin >> n;
    vector<Node> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].x;
    for (int i = 0; i < n; i++) cin >> a[i].r;
    for (int i = 0; i < n; i++) cin >> a[i].w;

    sort(a.begin(), a.end(), cmp);
    /*
    for(int i=0;i<n;i++)
    {
            cout<<a[i].x<<","<<a[i].r<<"["<<a[i].x-a[i].r<<","<<a[i].x+a[i].r<<"]"<<endl;
    }
    cout<<endl;*/
    prefix[0] = a[0].w;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + a[i].w;  //权值前缀和
    }

    int ans = -1;

    for (int i = 0; i < n; i++) {
        // cout<<"Node"<<i<<": ";
        int l, r;
        int askl = a[i].x - a[i].r;
        int askr = a[i].x + a[i].r;
        l = check(askl, a);  //找到第一个大于等于 askl的点
        // cout<<l<<" ";
        r = check(askr, a);  //找到第一个大于等于 askr的点
        if (a[r].x > askr)
            r--;
        // cout<<r<<" "<<endl;
        if (l == 0)
            ans = max(ans, prefix[r]);
        else
            ans = max(ans, prefix[r] - prefix[l - 1]);
    }

    cout << ans << endl;
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int t = 1;
    while (t--) solve();
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：14 ms
内存：996 KiB

输入文件（1.in） 

18467
-11055 15965 3634 4037 5251 26848 18865 27985 1792 -7703 8203 2901 17070 21332 3619 4810 -957
<285249 bytes omitted>

答案文件（1.out） 

9085258

用户输出 

9085258

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：14 ms
内存：924 KiB

输入文件（2.in） 

18810
25525 19477 -22724 24353 15064 31473 -19526 -13477 3128 20194 28070 18537 -31362 14575 14131 
<290709 bytes omitted>

答案文件（2.out） 

9334962

用户输出 

9334962

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：60 ms
内存：3552 KiB

输入文件（3.in） 

100000
537277652 151018213 90613924 45444816 137475011 116822218 472518803 207521551 382084796 7938
<1937139 bytes omitted>

答案文件（3.out） 

27864

用户输出 

27864

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：633 ms
内存：31684 KiB

输入文件（4.in） 

1000000
453551192 -68660045 121403219 -86588435 -533232215 45978151 3018392 65944827 15294959 -3607
<19376810 bytes omitted>

答案文件（4.out） 

284130

用户输出 

284130

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：637 ms
内存：31672 KiB

输入文件（5.in） 

1000000
147839651 -77411845 -123840575 91831923 122810270 713492817 169564700 90604635 -112846715 1
<19377621 bytes omitted>

答案文件（5.out） 

250089

用户输出 

250089

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：637 ms
内存：31728 KiB

输入文件（6.in） 

1000000
305471927 8815049 19205431 188592786 -768751815 673804965 -361267615 66736271 469983128 743
<18147391 bytes omitted>

答案文件（6.out） 

22867

用户输出 

22867

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：620 ms
内存：31728 KiB

输入文件（7.in） 

1000000
29624159 292640154 -466020835 153129762 197982402 -641561065 859459451 -523894390 -66405635
<18149690 bytes omitted>

答案文件（7.out） 

24177

用户输出 

24177

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：619 ms
内存：31732 KiB

输入文件（8.in） 

1000000
-676235015 763010181 345441587 243629683 250145873 619479926 -492353405 397072791 309122003
<18149183 bytes omitted>

答案文件（8.out） 

24637

用户输出 

24637

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：618 ms
内存：31736 KiB

输入文件（9.in） 

1000000
357446663 -19100180 18372614 3604481 378517151 549785571 -327370670 96482158 178358607 -632
<18150221 bytes omitted>

答案文件（9.out） 

23584

用户输出 

23584

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：602 ms
内存：31732 KiB

输入文件（10.in） 

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3
<22320514 bytes omitted>

答案文件（10.out） 

1000000000000000

用户输出 

1000000000000000

系统信息 

Exited with return code 0
CQUPT OJ Powered by SYZOJ.