oj.uz

Submission #1116346

# Submission time Handle Problem Language Result Execution time Memory
1116346 2024-11-21T14:19:59 Z staszic_ojuz Semiexpress (JOI17_semiexpress) C++17
100 / 100
 2 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    int a,b,c;
    cin>>a>>b>>c;
    long long t;
    cin>>t;
    long long express[m+1];
    int ans = 0;
    for(int i = 0;i<m;i++)
    {
        cin>>express[i];
        express[i]--;
    }
    priority_queue<vector<long long>> pq;
    queue<vector<long long>> q;
    //dodaæ punkty za stacje expresu
    // {wynik,czas na pocz¹tku,pozycja,najbli¿sza stacja w prawo};
    for(int i = 0;i<m-1;i++)
    {
        if(express[i]*b <= t)
        {
            q.push({(long long)min((t-express[i]*b)/a+1,(long long)express[i+1]-express[i]),(long long)express[i]*b,express[i],express[i+1]});
            int spoz = q.front()[2];
            spoz+=q.front()[0];
            long long czas = q.front()[1]+(spoz-q.front()[2])*c;
            ans+=q.front()[0];
            if(spoz < q.front()[3]&& czas<=t)
            {
                int wynik = min(q.front()[3]-spoz,(t-czas)/a+1);

                int naj = q.front()[3];

                pq.push({wynik,czas,spoz,naj});
            }
            q.pop();

        }

    }
    ans--;
    if(express[m-1]*b <=t) ans++;
    for(int i = 0;i<k-m;i++)
    {
        if(!pq.empty())
        {

            int spoz = pq.top()[2];
            spoz+=pq.top()[0];
            long long czas = pq.top()[1]+(spoz-pq.top()[2])*c;
            ans+=pq.top()[0];

            if(spoz < pq.top()[3]&& czas<=t)
            {
                int wynik = min(pq.top()[3]-spoz,(t-czas)/a+1);

                int naj = pq.top()[3];
                pq.pop();
                pq.push({wynik,czas,spoz,naj});
            }
            else
            {
                pq.pop();
            }
        }

    }
    cout<<ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 2 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 2 ms 592 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 2 ms 336 KB Output is correct
27 Correct 2 ms 336 KB Output is correct
28 Correct 2 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct