QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#96692#5488. Platform Placingmonkedluffy#AC ✓19ms4548kbC++231.2kb2023-04-15 03:35:512023-04-15 03:35:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-15 03:35:52]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:4548kb
  • [2023-04-15 03:35:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve(){
    ll n, s, k;
    cin >> n >> s >> k;
    if(n == 1){
        cout << k;
        return;
    }

    s = 2*s;
    k = 2*k;

    vector<ll> x(n);
    for(ll i = 0; i < n; i++){
        cin >> x[i];
        x[i] = 2*x[i];
    }

    sort(x.begin(), x.end());
    
    vector<ll> ans(n, s);
    ans[0] = min(2*(x[1] - x[0] - s/2), k); 
    bool ok = true;
    for(ll i = 1; i < n; i++){
        if(x[i] - x[i-1] < s){
            ok = false;
            break;
        }

        if(i < n-1) ans[i] = min(k, min(2*(x[i] - x[i-1] - ans[i-1]/2), 2*(x[i+1] - x[i] - s/2)));
        else ans[i] = min(2*(x[i] - x[i-1] - ans[i-1]/2), k);
    }

    // for(ll i = 0; i < n; i++){
    //     cout << ans[i] << " ";
    // }

    ll val = 0;
    for(ll i = 0; i < n; i++){
        val += ans[i];
    }

    val = val/2;

    if(!ok){
        cout << -1;
    }
    else{
        cout << val;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    while(t--){
        cout << fixed << setprecision(15);
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3324kb

input:

1 1 100
1

output:

100

result:

ok single line: '100'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3304kb

input:

4 1 4
1
6
8
10

output:

11

result:

ok single line: '11'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3404kb

input:

5 1 6
6
7
8
3
5

output:

7

result:

ok single line: '7'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3320kb

input:

2 5 10
1
2

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3304kb

input:

5 1 7
4
6
9
12
14

output:

13

result:

ok single line: '13'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

6 1 7
4
6
7
10
12
15

output:

14

result:

ok single line: '14'

Test #7:

score: 0
Accepted
time: 18ms
memory: 4524kb

input:

100000 27 27
1192240
694414
2285740
2431513
2689363
1355428
498097
1803142
732106
881470
1325728
1343656
9748
2245321
727246
1871047
2413504
1439857
537922
442315
1987174
199477
639766
62587
1345897
53515
1993600
589816
1302643
940114
1949941
1415152
864325
60886
2068579
99118
2681263
2055592
82432
...

output:

2700000

result:

ok single line: '2700000'

Test #8:

score: 0
Accepted
time: 14ms
memory: 4504kb

input:

100000 2 7
1102905
642790
2114975
2250117
2488738
1253837
461380
1667944
677697
815856
1226243
1242797
9119
2077719
673203
1730905
2233264
1332005
498076
409843
1838123
184873
592094
57976
1244889
49637
1844081
545985
1204965
870148
1803677
1309192
800070
56400
1913684
91794
2481302
1901591
76302
54...

output:

700000

result:

ok single line: '700000'

Test #9:

score: 0
Accepted
time: 19ms
memory: 4512kb

input:

100000 2 29
1103183
642683
2116228
2251006
2489444
1254224
460729
1669425
677344
815680
1226750
1243356
8996
2078906
672939
1732245
2234257
1332331
497537
409273
1839894
184141
592138
57887
1245371
49501
1845898
545761
1205459
870015
1805403
1309463
799864
56287
1915302
91537
2481975
1903294
76140
5...

output:

2388768

result:

ok single line: '2388768'

Test #10:

score: 0
Accepted
time: 18ms
memory: 4544kb

input:

100000 2 29
1325225
772465
2537704
2700474
2986537
1506368
553751
2002155
814213
979533
1473689
1493331
10839
2492832
808885
2077696
2680509
1599740
598390
492046
2206935
222198
712071
69789
1495841
59542
2214046
656249
1447904
1044222
2165624
1572517
960626
67919
2296960
110675
2977583
2282799
9196...

output:

2570562

result:

ok single line: '2570562'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3304kb

input:

5 99999 100000
1
100000001
200000001
300000001
400000001

output:

500000

result:

ok single line: '500000'

Test #12:

score: 0
Accepted
time: 18ms
memory: 4540kb

input:

100000 2 100000
1324112
771358
2536865
2698938
2985783
1504779
552992
2002276
813258
979425
1471862
1491711
10750
2492275
807847
2077489
2678959
1599052
597387
490845
2206254
221600
710581
69870
1494100
59767
2213217
655129
1446164
1044161
2165161
1571344
960350
67982
2296383
110348
2976623
2281957
...

output:

2899746

result:

ok single line: '2899746'

Test #13:

score: 0
Accepted
time: 19ms
memory: 4540kb

input:

100000 2 100000
9283106
5406596
17739889
18870564
20875424
10531550
3868578
13999549
5693451
6856226
10292857
10438831
75902
17431987
5655766
14522884
18730397
11188957
4178017
3428187
15429784
1541051
4981635
485774
10454386
413100
15479431
4593776
10117504
7311043
15137208
10999099
6719496
473237
...

output:

17763244

result:

ok single line: '17763244'

Test #14:

score: 0
Accepted
time: 18ms
memory: 4544kb

input:

100000 20 100000
9273198
5385844
17775976
18913022
20902851
10547069
3859081
14033989
5686971
6858335
10313021
10453406
73992
17470972
5649378
14570459
18767527
11203843
4167326
3421862
15461823
1536361
4959708
479964
10470451
414521
15511814
4569143
10133987
7314515
15175051
11008328
6720850
466988...

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0
Accepted
time: 10ms
memory: 4548kb

input:

100000 1 100000
44158
25720
84658
90057
99607
50202
18449
66784
27116
32648
49102
49766
362
83161
26936
69299
89390
53329
19924
16383
73600
7389
23696
2319
49849
1983
73838
21846
48247
34820
72221
52414
32013
2256
76615
3672
99307
76134
3054
21678
38878
15070
3269
95278
47256
92095
22029
75817
97642...

output:

100000

result:

ok single line: '100000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

3 1 4
1
2
3

output:

3

result:

ok single line: '3'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

2 4 9
1
7

output:

12

result:

ok single line: '12'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3380kb

input:

1000 100000 100000
11099958
29099860
70199667
6999976
56099723
46899774
70699666
89699573
16499930
92699565
79599622
32299845
36199827
299999
56799718
79299623
60299706
92999563
64399690
72099660
58999713
82699608
42099793
57899716
36399826
19299915
55199728
85299597
97199542
92399566
35299831
91299...

output:

-1

result:

ok single line: '-1'