Submission #484699

#TimeUsernameProblemLanguageResultExecution timeMemory
484699Haruto810198Semiexpress (JOI17_semiexpress)C++17
100 / 100
15 ms4548 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int, int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int MAX = 3010; int n, m, k; int a, b, c; int T; pii seg[MAX]; vi vals; int res; void solve(int id){ int from = seg[id].F; int to = seg[id].S; int rem_T = T - (from - 1) * b; if(rem_T < 0) return; int ptr = from; int next_tle = ptr + (rem_T + a) / a; if(next_tle >= to + 1) next_tle = to + 1; res += next_tle - ptr; rem_T -= (next_tle - ptr) * c; ptr = next_tle; int cnt = 0; while(rem_T >= 0 and ptr <= to){ next_tle = ptr + (rem_T + a) / a; if(next_tle >= to + 1) next_tle = to + 1; vals.pb(next_tle - ptr); rem_T -= (next_tle - ptr) * c; ptr = next_tle; cnt++; if(cnt == k - m) return; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>k; cin>>a>>b>>c; cin>>T; FOR(i, 1, m, 1){ cin>>seg[i].F; } FOR(i, 1, m-1, 1){ seg[i].S = seg[i+1].F - 1; } FOR(i, 1, m-1, 1){ solve(i); } //cerr<<"res = "<<res<<endl; //cerr<<"vals : "; for(int i : vals){ //cerr<<i<<" "; } //cerr<<endl; sort(vals.begin(), vals.end()); reverse(vals.begin(), vals.end()); int cnt = min(k - m, szof(vals)); FOR(i, 0, cnt - 1, 1){ res += vals[i]; } res--; if(b * (n-1) <= T) res++; cout<<res<<'\n'; return 0; }

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:89:10: warning: unused variable 'i' [-Wunused-variable]
   89 |  for(int i : vals){
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...