Submission #1116346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116346		staszic_ojuz	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	2 ms	592 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52