QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138418 | #366. Long Distance Coach | Rafi22# | 0 | 2ms | 10536kb | C++14 | 1.8kb | 2023-08-11 18:10:00 | 2024-07-04 01:36:57 |
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=2000000007;
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--)
{
// cout<<S<<" ";
DP[i]=min(DP[i],DP[j]+S);
S+=C[j].nd;
S-=((x-C[j].st)/t+1-val[j])*w;
}
// cout<<endl;
for(auto [l,c]:W[i])
{
for(int j=l;j<=i;j++) val[i]=min(val[i],c);
}
// cout<<DP[i]<<" ";
}
// cout<<endl;
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: 0
Wrong Answer
time: 2ms
memory: 10536kb
input:
999999999999 1 1 1000000 4 1 2 3
output:
252000000007000003
result:
wrong answer 1st lines differ - expected: '499999999999000003', found: '252000000007000003'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%