QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188589#5488. Platform PlacingGamal74#WA 13ms4656kbC++201.8kb2023-09-26 03:14:192023-09-26 03:14:20

Judging History

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

  • [2023-09-26 03:14:20]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:4656kb
  • [2023-09-26 03:14:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl

void Gamal() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};

const double EPS = 1e-9;
const ll OO = 0X3F3F3F3F3F3F3F3F;
const int N = 2e5 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;


void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<ll> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(all(v));
    vector<ll> mx(n,r);
    for (int i = 0; i < n; ++i) {
        if(i)mx[i] = min(mx[i],2 * (v[i] - v[i - 1]));
        if (i != n - 1)mx[i] = min(mx[i], 2 * (v[i + 1] - v[i]));
    }
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        if(mx[i] < l)continue;
        if (i != n - 1 && mx[i + 1] >= l) {
            // x  <= 2 * v[i + 1] - 2 * v[i] - l
            ll x = 2 * v[i + 1] - 2 * v[i] - l;
            mx[i] = min(mx[i], x);
        }
        ans += mx[i];
        if (i != n - 1) {
            mx[i + 1] = min(mx[i + 1], 2 * (v[i + 1] - v[i]) - mx[i]);
        }
    }
    if(ans == 0)ans = -1;
    cout << ans;
}


signed main() {
    Gamal();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3464kb

input:

1 1 100
1

output:

100

result:

ok single line: '100'

Test #2:

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

input:

4 1 4
1
6
8
10

output:

11

result:

ok single line: '11'

Test #3:

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

input:

5 1 6
6
7
8
3
5

output:

7

result:

ok single line: '7'

Test #4:

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

input:

2 5 10
1
2

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

5 1 7
4
6
9
12
14

output:

13

result:

ok single line: '13'

Test #6:

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

input:

6 1 7
4
6
7
10
12
15

output:

14

result:

ok single line: '14'

Test #7:

score: 0
Accepted
time: 12ms
memory: 4652kb

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: 12ms
memory: 4576kb

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: 8ms
memory: 4616kb

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: 9ms
memory: 4648kb

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: 1ms
memory: 3428kb

input:

5 99999 100000
1
100000001
200000001
300000001
400000001

output:

500000

result:

ok single line: '500000'

Test #12:

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

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: 6ms
memory: 4608kb

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: -100
Wrong Answer
time: 13ms
memory: 4656kb

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:

17673480

result:

wrong answer 1st lines differ - expected: '-1', found: '17673480'