Submission #169500

#	Time	Username	Problem	Language	Result	Execution time	Memory
169500		combi1k1	Semiexpress (JOI17_semiexpress)	C++14	48 / 100	1084 ms	214364 KiB

semiexpress

#include<bits/stdc++.h>

using namespace std;

#define ll  long long
#define X   first
#define Y   second

#define all(x)  x.begin(),x.end()
#define sz(x)   (int)x.size()

#define pb      emplace_back
#define endl    "\n"

const ll    inf = 1e18;
const int   N   = 2e5 + 5;

typedef pair<int,int>   ii;

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, k, m;    cin >> n >> m >> k;     k -= m;
    ll  A, B, C;    cin >> A >> B >> C;

    ll  T;  cin >> T;

    vector<int> s(m);
    vector<int> pot;

    int ans = -1;

    for(int i = 0 ; i < m ; ++i)    cin >> s[i];
    for(int i = 1 ; i < m ; ++i)    {
        ll  rem = T - B * (s[i - 1] - 1);
        int rig = s[i - 1];

        if (rem < 0)
            break;

        auto jump = [&]()   {
            if (rem < 1)    {
                rig = s[i];
                return  0;
            }
            ll  nxt = rig + rem / A + 1;

            if (nxt > s[i])
                nxt = s[i];

            ll  len = nxt - rig;

            rig += len;
            rem -= len * C;

            return  (int)len;
        };

        ans += jump();

        while (rig < s[i])
            pot.pb(jump());
    }

    if (B * (n - 1) <= T)
        ans++;

    sort(pot.begin(),pot.end(),greater<ll>());

    if (k > sz(pot))
        k = sz(pot);

    cout << ans + accumulate(pot.begin(),pot.begin() + k,0) << endl;
}
/*
300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
*/

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 0 / 52