Submission #363498

#	Time	Username	Problem	Language	Result	Execution time	Memory
363498		cute_hater	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	3 ms	512 KiB

semiexpress

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

struct Ask {
    int fst, nxt, cur, exp, sexp, us, t;

    Ask() {};
    Ask(int fst, int nxt, int cur, int exp, int sexp, int us, int t) : fst(fst), nxt(nxt), cur(cur), exp(exp), sexp(sexp), us(us), t(t) {};
};

bool operator < (Ask t1, Ask t2) {
    int tm1 = t1.fst * t1.exp + (t1.cur - t1.fst) * t1.sexp, tm2 = t2.fst * t2.exp + (t2.cur - t2.fst) * t2.sexp;
    int nxt1 = min(t1.nxt, t1.cur + (t1.t - tm1) / t1.us + 1), nxt2 = min(t2.nxt, t2.cur + (t2.t - tm2) / t2.us + 1);
    int add1 = min(t1.nxt - nxt1, (t1.t - (t1.fst * t1.exp + (nxt1 - t1.fst) * t1.sexp)) / t1.us + 1);
    int add2 = min(t2.nxt - nxt2, (t2.t - (t2.fst * t2.exp + (nxt2 - t2.fst) * t2.sexp)) / t2.us + 1);
    if (t1.fst * t1.exp + (nxt1 - t1.fst) * t1.sexp > t1.t)
        add1 = 0;
    if (t2.fst * t2.exp + (nxt2 - t2.fst) * t2.sexp > t2.t)
        add2 = 0;
    return add1 > add2 || add1 == add2 && t1.fst < t2.fst;
}

void solve() {
    int n, m, k, us, exp, sexp, t;
    cin >> n >> m >> k >> us >> exp >> sexp >> t;
    k -= m;
    vector <int> s(m);
    loop(i, m) {
        cin >> s[i];
        --s[i];
    }
    set <Ask> ask;
    int ans = -1 + (exp * (n - 1) <= t);
    loop(i, m - 1) {
        if (s[i] * exp > t) break;
        ans += min(s[i + 1] - s[i], (t - (s[i] * exp)) / us + 1);
        ask.insert(Ask(s[i], s[i + 1], s[i], exp, sexp, us, t));
    }
    loop(i, k) {
        Ask t1 = *ask.begin();
        ask.erase(ask.begin());
        int tm1 = t1.fst * t1.exp + (t1.cur - t1.fst) * t1.sexp;
        int nxt1 = min(t1.nxt, t1.cur + (t1.t - tm1) / t1.us + 1);
        int add1 = min(t1.nxt - nxt1, (t1.t - (t1.fst * t1.exp + (nxt1 - t1.fst) * t1.sexp)) / t1.us + 1);
        if (t1.fst * t1.exp + (nxt1 - t1.fst) * t1.sexp > t1.t)
            add1 = 0;
        ans += add1;
        ask.insert(Ask(t1.fst, t1.nxt, nxt1, exp, sexp, us, t));
    }
    cout << ans;
}

signed main() {
    //freopen("dream.in", "r", stdin);
    //freopen("dream.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Compilation message (stderr)

semiexpress.cpp: In function 'bool operator<(Ask, Ask)':
semiexpress.cpp:67:40: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   67 |     return add1 > add2 || add1 == add2 && t1.fst < t2.fst;
      |                           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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