QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#188586 | #5488. Platform Placing | Gamal74# | WA | 15ms | 4632kb | C++20 | 1.9kb | 2023-09-26 03:10:53 | 2023-09-26 03:10:53 |
Judging History
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 (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;
if (x >= l)mx[i] = min(mx[i], x);
}
if (mx[i] >= l) {
ans += mx[i];
if (i != n - 1) {
// v[i + 1] - v[i] + mx[i] >= x
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: 0ms
memory: 3432kb
input:
1 1 100 1
output:
100
result:
ok single line: '100'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
4 1 4 1 6 8 10
output:
11
result:
ok single line: '11'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
5 1 6 6 7 8 3 5
output:
7
result:
ok single line: '7'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
2 5 10 1 2
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
5 1 7 4 6 9 12 14
output:
13
result:
ok single line: '13'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
6 1 7 4 6 7 10 12 15
output:
14
result:
ok single line: '14'
Test #7:
score: 0
Accepted
time: 15ms
memory: 4620kb
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: 13ms
memory: 4620kb
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: 14ms
memory: 4592kb
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: 4612kb
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: 3424kb
input:
5 99999 100000 1 100000001 200000001 300000001 400000001
output:
500000
result:
ok single line: '500000'
Test #12:
score: 0
Accepted
time: 7ms
memory: 4592kb
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: 14ms
memory: 4632kb
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: 14ms
memory: 4628kb
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:
17673470
result:
wrong answer 1st lines differ - expected: '-1', found: '17673470'