QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138426 | #366. Long Distance Coach | Rafi22# | 0 | 3ms | 10836kb | C++14 | 1.7kb | 2023-08-11 18:16:02 | 2024-07-04 01:37:00 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=100000000000000007;
int mod=1000000007;
int mod1=998244353;
const int N=200007;
map<int,vector<int>>M;
vector<pair<int,int>>W[N];
int DP[N];
int val[N];
void add(int l,int r,int c)
{
// cout<<"JEST "<<l<<" "<<r<<" "<<c<<endl;
W[r].pb({l,c});
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x,n,m,w,t;
cin>>x>>n>>m>>w>>t;
int ans=x/t+1;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
M[a/t].pb(a%t);
}
M[x/t].pb(x%t);
vector<pair<int,int>>C(m+1);
C[0].st=-inf;
for(int i=1;i<=m;i++)
{
cin>>C[i].st>>C[i].nd;
ans+=(x-C[i].st)/t+1;
}
ans*=w;
sort(all(C));
for(auto [p,y]:M)
{
vector<int>V=y;
sort(all(V));
int l=1;
for(auto i:V)
{
int r=--lower_bound(all(C),make_pair(i,0LL))-C.begin();
if(l<=r) add(l,r,p);
l=r+1;
}
}
for(int i=1;i<=m;i++) val[i]=inf;
for(int i=1;i<=m+1;i++)
{
int S=0;
DP[i]=inf;
for(int j=i-1;j>=0;j--)
{
DP[i]=min(DP[i],DP[j]+S);
S+=C[j].nd;
S-=((x-C[j].st)/t+1-val[j])*w;
}
for(auto [l,c]:W[i])
{
for(int j=l;j<=i;j++) val[j]=min(val[j],c);
}
}
cout<<ans+DP[m+1]<<endl;
return 0;
}
/*
19 1 4 8 7
10
1 20
2 10
4 5
6 5
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 16
Accepted
time: 3ms
memory: 10684kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
499999999999000003
result:
ok single line: '499999999999000003'
Test #2:
score: 16
Accepted
time: 0ms
memory: 10096kb
input:
5 1 1 15 4 2 3 4
output:
45
result:
ok single line: '45'
Test #3:
score: 16
Accepted
time: 2ms
memory: 9904kb
input:
5 1 1 15 4 3 2 13
output:
43
result:
ok single line: '43'
Test #4:
score: 16
Accepted
time: 2ms
memory: 10708kb
input:
5 1 1 15 4 3 2 19
output:
45
result:
ok single line: '45'
Test #5:
score: 16
Accepted
time: 2ms
memory: 9976kb
input:
142 4 7 10 13 67 44 86 141 3 1000000000 6 1000000000 9 1000000000 1 60 4 81 7 48 10 14
output:
878
result:
ok single line: '878'
Test #6:
score: 16
Accepted
time: 2ms
memory: 9240kb
input:
142 3 8 10 13 68 46 37 4 1000000000 8 1000000000 1 61 2 59 5 79 6 79 9 20 10 155
output:
982
result:
ok single line: '982'
Test #7:
score: 16
Accepted
time: 0ms
memory: 10836kb
input:
150 8 8 10 18 5 88 75 87 83 14 109 112 17 30 7 70 2 24 10 25 12 34 9 92 8 30 13 18
output:
463
result:
ok single line: '463'
Test #8:
score: 16
Accepted
time: 0ms
memory: 10244kb
input:
10000000000 8 8 6 18 9547257284 4226673527 9454195771 9513946487 7287482436 6692534804 3951479147 8774939403 12 415893810 4 735304001 13 184845346 14 354080601 15 455062532 16 886416267 3 985580216 1 97417991
output:
18443869092
result:
ok single line: '18443869092'
Test #9:
score: 16
Accepted
time: 2ms
memory: 9624kb
input:
200 4 8 5 14 136 180 37 58 13 39 8 100 3 33 11 32 6 62 5 1 7 98 1 32
output:
601
result:
ok single line: '601'
Test #10:
score: 16
Accepted
time: 2ms
memory: 10268kb
input:
200 8 8 5 18 73 40 168 152 10 12 122 178 3 46 5 30 7 18 9 40 11 24 13 12 15 17 17 9
output:
370
result:
ok single line: '370'
Test #11:
score: 16
Accepted
time: 2ms
memory: 9448kb
input:
99999999999 7 7 3 16 75171012465 68638795379 63875989701 83563043959 64144786889 89597405323 74981605181 2 105022615 4 341401908 6 209850215 8 507409549 10 849182839 12 760157370 14 257217651
output:
116398917650
result:
ok single line: '116398917650'
Test #12:
score: 16
Accepted
time: 2ms
memory: 9636kb
input:
150 8 8 10 18 146 49 17 101 117 134 131 33 1 1 3 1 7 5215 12 2283658 4 69 14 23058601 16 170888234 10 148221
output:
751
result:
ok single line: '751'
Test #13:
score: 16
Accepted
time: 0ms
memory: 9628kb
input:
8001 7 8 6 17 3613 4410 5581 2885 1918 934 6395 10 131687242 13 284628020 2 541922 15 554928957 4 4115226 6 17341529 1 16935 8 52922149
output:
25422
result:
ok single line: '25422'
Test #14:
score: 16
Accepted
time: 0ms
memory: 10588kb
input:
250 8 8 10 18 238 189 86 221 120 173 53 205 6 300728 13 24836451 8 2800753 15 946925513 2 293 10 17341529 1 251803956 3 16935
output:
1260
result:
ok single line: '1260'
Test #15:
score: 16
Accepted
time: 2ms
memory: 9608kb
input:
1234567 8 8 1000000 18 2 22 42 62 82 102 122 142 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1
output:
137203000007
result:
ok single line: '137203000007'
Test #16:
score: 16
Accepted
time: 0ms
memory: 10560kb
input:
1234567 8 8 999 18 449660 490828 187404 376334 697798 1177644 1056704 312928 3 996683357 5 928740029 7 950657139 9 904761397 11 923725553 13 962648669 15 971692610 17 965766352
output:
616666716
result:
ok single line: '616666716'
Test #17:
score: 16
Accepted
time: 0ms
memory: 9464kb
input:
200 8 8 12 18 131 170 55 60 47 28 158 192 13 40 16 87 17 69 4 55 7 99 9 975663280 15 17 3 912112332
output:
1159
result:
ok single line: '1159'
Test #18:
score: 0
Wrong Answer
time: 2ms
memory: 10816kb
input:
600 8 8 63 18 340 333 326 328 331 339 332 337 5 17 3 12 11 26 14 18 12 943485371 17 25 10 954990891 1 48
output:
-5846744072754548886
result:
wrong answer 1st lines differ - expected: '15089', found: '-5846744072754548886'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%