oj.uz

Submission #363498

# Submission time Handle Problem Language Result Execution time Memory
363498 2021-02-06T09:33:11 Z cute_hater Semiexpress (JOI17_semiexpress) C++17
100 / 100
 3 ms 512 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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