Submission #362011

#	Time	Username	Problem	Language	Result	Execution time	Memory
362011		Olerinskiy	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	492 KiB

semiexpress

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert> 
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>
#include <stack>
#include <limits>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

istream& operator>> (istream& in, pii& b) {
    in >> b.first >> b.second;
    return in;
}

ostream& operator<< (ostream& out, const pii& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template<typename T> ostream& operator<< (ostream& out, const vector<T>& a) {
    for (auto k : a) out << k << " ";
    return out;
}

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << endl;
    const long long INF = 1e18;
    // const long long mod = 2600000069;
    // const long long p = 10;
#else
    #define dbg(x) 57
    const long long INF = 1e18;
    // const long long mod = 2600000069;  
    // const long long p = 179;
#endif

const ld PI = 4 * atan(1);

#define time clock() / (double) CLOCKS_PER_SEC

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,sse3,sse4")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("avx2")

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 3100;

int n, m, k;
int a, b, c;
int t;
int s[N];
int firstbad[N];

int count(int i) {
    if (firstbad[i] >= s[i + 1] || ((t - (s[i] - 1) * b - (firstbad[i] - s[i]) * c)) < 0) return 0;
    assert(i <= m);
    return min(s[i + 1] - firstbad[i], (t - (s[i] - 1) * b - (firstbad[i] - s[i]) * c) / a + 1);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    for (int i = 0; i < m; i++) {
        cin >> s[i];
    }
    int ans = 0;
    set<pii, greater<pii>> order; // {add, pos}
    for (int i = 0; i < m - 1; i++) {
        if ((s[i] - 1) * b > t) break;
        int can = min(s[i + 1] - s[i] - 1, (t - (s[i] - 1) * b) / a);
        ans += 1 + can;
        firstbad[i] = s[i] + can + 1;
        if (firstbad[i] < s[i + 1]) {
            order.insert({count(i), i});
        }
    }
    if ((n - 1) * b <= t) ans++;
    for (int i = 0; i < k - m; i++) {
        if (order.empty()) break;
        auto[add, ind] = *order.begin();
        order.erase(order.begin());
        ans += add;
        firstbad[ind] += add;
        add = count(ind);
        if (add > 0) {
            order.insert({add, ind});
        }
    }
    cout << ans - 1 << "\n";
}
/*
10 3 5 
10 3 5 
30
1 6 10
-> 8

10 3 5 
10 3 5 
25
1 6 10
-> 7

90 10 12
100000 1000 10000
10000
1
10
20
30
40
50
60
70
80
90
-> 2

300 8 16
345678901 123456789 234567890
12345678901
1
10
77
82
137
210
297
300
-> 72

1000000000 2 3000
1000000000 1 2
1000000000
1
1000000000
-> 3000
*/

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