QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138422#366. Long Distance CoachRafi22#0 3ms11180kbC++141.8kb2023-08-11 18:13:432024-07-04 01:36:58

Judging History

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

  • [2024-07-04 01:36:58]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:11180kb
  • [2023-08-11 18:13:43]
  • 提交

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--)
        {
         //   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: 16
Accepted
time: 3ms
memory: 9664kb

input:

999999999999 1 1 1000000 4
1
2 3

output:

499999999999000003

result:

ok single line: '499999999999000003'

Test #2:

score: 0
Accepted
time: 3ms
memory: 11024kb

input:

5 1 1 15 4
2
3 4

output:

45

result:

ok single line: '45'

Test #3:

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

input:

5 1 1 15 4
3
2 13

output:

43

result:

ok single line: '43'

Test #4:

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

input:

5 1 1 15 4
3
2 19

output:

45

result:

ok single line: '45'

Test #5:

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

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
Wrong Answer
time: 0ms
memory: 10480kb

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:

988

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%