Submission #590336

#TimeUsernameProblemLanguageResultExecution timeMemory
590336GilwallSemiexpress (JOI17_semiexpress)C++14
100 / 100
10 ms356 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define eb emplace_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define sq(a) ((a)*(a)) #define MOO(i,a,b) for (int i=a; i<b; i++) #define M00(i,a) for (int i=0; i<a; i++) #define MOOd(i,a,b) for (int i = (b)-1; i >= a; i--) #define M00d(i,a) for (int i = (a)-1; i >= 0; i--) #define per(i,a,b) for (int i = (b)-1; i >= a; i--) #define rep(i,a,b) for (int i=a; i<b; i++) #define FOR(i,a,b) for (int i=a; i<b; i++) #define F0R(i,a) for (int i=0; i<a; i++) #define ROF(i,a,b) for (int i = (b)-1; i >= a; i--) #define R0F(i,a) for (int i = (a)-1; i >= 0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << endl, 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << endl; #define _<< " _ " << #define int long long typedef long double ld; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; typedef vector<int> vi; typedef vector<ld> vld; typedef vector<vector<int>> vvi; const ld PI = acos(-1.0); const ld EPS = 1e-7; const int MOD = 1e9+7; int POW(int b, int e) { int r = 1; while(e) { if(e % 2 == 1) { r *= b; r %= MOD; } e /= 2; b *= b; b %= MOD; } return r; } int gcd(int a, int b) { if(b > a) return gcd(b,a); if(b == 0) return a; return gcd(b, a % b); } int INV(int a) { return POW(a, MOD-2); } //Constants and Variables here int n, m, k; int A, B, C; int T; vi express; vector<bool> added(3000, false); int tot = 0; int f(int e, int numstop) { int l = express[e]; int r = express[e+1]; vi semi; semi.pb(l); if(!added[e]) { int time = T - (l-1) * B; int loc = time / A; int delta = min(r-1, l + loc) - l + 1; if(time < 0) delta = 0; tot += delta; added[e] = true; } M00(i, numstop) { int semistop = semi.back(); int time = T - (l-1) * B - (semistop - l) * C; int loc = time / A; if(time < A) { loc = 0; } semi.pb(semistop + loc + 1); } int semistop = semi.back(); int time = T - (l-1) * B - (semistop - l) * C; int loc = time / A; //semi stop to semistop + loc int extra = max(0ll, min(r-1, semistop + loc) - semistop + 1); if(time < 0) extra = 0; return extra; } int32_t main() { FAST mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); cin >> n >> m >> k >> A >> B >> C >> T; express.resize(m); M00(i, m) cin >> express[i]; express.pb(n+1); priority_queue<pi> Q; vi nums(m, 1); M00(i, m) { Q.push(mp(f(i, 1), i)); } M00(i, k - m) { auto p = Q.top(); Q.pop(); tot += p.f; int e = p.s; nums[e] += 1; Q.push(mp(f(e, nums[e]), e)); } cout << tot-1 << endl; }

Compilation message (stderr)

semiexpress.cpp:29:9: warning: ISO C++11 requires whitespace after the macro name
   29 | #define _<< " _ " <<
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...