Submission #1051749

#TimeUsernameProblemLanguageResultExecution timeMemory
1051749VahanAbrahamSemiexpress (JOI17_semiexpress)C++17
100 / 100
10 ms6100 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cstdio> #include <sstream> #include <map> #include <stack> #include <set> #include <queue> #include <list> #include <unordered_set> #include <unordered_map> #include <math.h> #include <bitset> #include <cmath> #include <vector> #include <iomanip> #include <random> #include <chrono> #include <cassert> using namespace std; #define ll long long #define fr first #define sc second #define pb push_back #define US freopen(".in", "r", stdin); freopen("j.out", "w", stdout); ll gcd(ll a, ll b) { if (a == 0 || b == 0) { return max(a, b); } if (a <= b) { return gcd(a, b % a); } else { return gcd(a % b, b); } } ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; } const int N = 300005; const ll oo = 100000000000000000, MOD = 1000000007; ll s[N]; void solve() { ll n; int m, k; ll A, B, C; ll T; cin >> n >> m >> k >> A >> B >> C >> T; for (int i = 1; i <= m; ++i) { cin >> s[i]; } ll ans = 0; vector<ll> vec; int diff = k - m; for (int i = 1; i <= m-1;++i) { ll sum = (s[i]-1) * B; ll cnt = T - sum; if (cnt >= 0) { ans++; cnt /= A; if (s[i] + cnt >= s[i + 1]) { //cout << ":AS " << i << endl; ans += (s[i + 1] - 1 - (s[i] + 1)) + 1; } else { ans += cnt; } ll last = s[i] + cnt; ll sum2 = 0; for (int j = 1; j <= diff; ++j) { if (last + 1 < s[i + 1]) { ll sum1 = (s[i] - 1) * B + C * (last + 1 - s[i]); cnt = T - sum1; if (cnt < 0) { break; } else { cnt /= A; if (last + cnt + 1 < s[i + 1]) { vec.pb(cnt + 1); //sum2 += vec.back(); } else { vec.pb((s[i + 1] - 1 - (last + 1)) + 1); //sum2 += vec.back(); } } last = last + 1 + cnt; } else { break; } } //cout << i << " " << sum2 << endl; } //cout << i << " " << ans << endl; } if ((n-1) * B <= T) { ++ans; } //cout <<"BOOM "<< ans << endl; int q = 0; sort(vec.begin(), vec.end()); for (int i = vec.size()-1; i >= 0; --i) { if (q >= diff) { break; } //cout << vec[i] << endl; ans += vec[i]; ++q; } cout << ans - 1 << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //US int tt = 1; //cin >> tt; while (tt--) { solve(); } }

Compilation message (stderr)

semiexpress.cpp: In function 'void solve()':
semiexpress.cpp:79:16: warning: unused variable 'sum2' [-Wunused-variable]
   79 |             ll sum2 = 0;
      |                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...