Submission #46642

#	Time	Username	Problem	Language	Result	Execution time	Memory
46642		kuzmichev_dima	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	23 ms	1000 KiB

semiexpress

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

int main() {
#ifdef LOCAL
    freopen("inp", "r", stdin);
    //freopen("outp", "w", stdout);
#else
    // freopen(TASKNAME ".in", "r", stdin);
    // freopen(TASKNAME ".out", "w", stdout);
#endif
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    i64 A, B, C, T;
    cin >> A >> B >> C >> T;
    vi exp(m);
    forn(i, m)
        scanf("%d", &exp[i]);
    int ans = -1;
    vi next(m);
    forn(i, m - 1) {
        i64 base_time = B * (exp[i] - 1);
        if (base_time > T) {
            next[i] = -1;
            continue;
        }
        //base_time + x * A <= T
        i64 x = (T - base_time) / A;
      //  cout << "base_time =" << base_time << " x = " << x << endl;
        if (x >= exp[i + 1] - exp[i]) {
             next[i] = -1;
             ans += exp[i + 1] - exp[i];
             continue;
        }
        next[i] = exp[i] + x + 1;
      //  printf("start next[%d] = %d\n", i, next[i]);
        ans += next[i] - exp[i];
    }
    if (B * (exp[m - 1] - 1) <= T)
        ans++;
   // cout << "start ans = " << ans << endl;
    forn(iter, k - m) {
       // printf("\n==============\n");
        pii best = {-1, -1};
        forn(i, m - 1) {
            if (next[i] == -1)
                continue;
            i64 base_time = B * (exp[i] - 1) + C * (next[i] - exp[i]);
            if (base_time > T) {
                next[i] = -1;
                continue;
            }
            //printf("i = %d base_time = %lld\n", i, base_time);
            //base_time + x * A <= T
            //x * A <= T - base_time
            //x <= (T - base_time) / A
            i64 x = min((T - base_time) / A, (i64)exp[i + 1] - next[i] - 1);
            //printf("iter = %d i = %d\n", iter, i);
            //cout << "x = " << x << endl;
            pii nnew = {x, i};
            best = max(best, nnew);
        }
        if (best.fi == -1)
            break;
        ans += best.fi + 1;
        int i = best.se;
        next[i] += best.fi + 1;
        if (next[i] >= exp[i + 1]) {
            next[i] = -1;
        } else {
            i64 base_time = B * (exp[i] - 1) + C * (next[i] - exp[i]);
            if (base_time > T)
                next[i] = -1;
        }
      //  printf("added i = %d next[i] = %d\n", i, next[i]);
    }
    printf("%d", ans);
}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &exp[i]);
         ~~~~~^~~~~~~~~~~~~~~

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