Submission #1275410

#TimeUsernameProblemLanguageResultExecution timeMemory
1275410vibeduckJobs (BOI24_jobs)C++20
29 / 100
73 ms19512 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define pf push_front #define mp make_pair #define fi first #define se second #define int long long #define all(x) (x).begin(), (x).end() typedef long double ld; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<bool> vb; typedef vector<vector<int>> vvi; typedef vector<vector<bool>> vvb; typedef vector<vector<ll>> vvll; typedef vector<string> vs; typedef vector<vector<string>> vvs; typedef vector<char> vc; typedef vector<vector<char>> vvc; typedef map<int, int> mii; typedef unordered_map<int, int> umii; const int mod = 1e9 + 7; const int inf = INTMAX_MAX; const bool tc = false; int n, s; int ans = 0; struct chain { vi v; int ptr; }; inline void solve() { cin >> n >> s; vector<chain> vc; for (int i = 0; i < n; i++) { int x, p; cin >> x >> p; if (p == 0) { chain c; c.v = {x}; c.ptr = 0; vc.pb(c); continue; } vc.back().v.pb(x); } // minimum loss at a point for positive profit priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> st; // {maxloss, {profit, index}} for (int i = 0; i < vc.size(); i++) { pii tmp = {0, 0}; // {profit, maxloss} bool ok = false; for (int j = vc[i].ptr; j < vc[i].v.size(); j++) { tmp.fi += vc[i].v[j]; tmp.se = min(tmp.se, tmp.fi); vc[i].ptr++; if (tmp.fi >= 0) { ok = true; break; } // check this } if (ok) st.push({-tmp.se, {tmp.fi, i}}); } while (st.size()) { auto cur = st.top(); int ml = cur.fi; int p = cur.se.fi; int i = cur.se.se; //cout << "money: " << s << '\n'; //cout << ml << " loss for " << p << " profit at " << i << '\n'; if (ml > s) { //cout << "done, too much loss\n"; break; } ans += p; s += p; // recalculate for that chain // vc[i] st.pop(); pii tmp = {0, 0}; bool ok = false; for (int j = vc[i].ptr; j < vc[i].v.size(); j++) { tmp.fi += vc[i].v[j]; tmp.se = min(tmp.se, tmp.fi); vc[i].ptr++; //cout << "at " << j << " " << tmp.fi << " " << tmp.se << '\n'; if (tmp.fi > 0) { ok = true; break; } // check this } //if (ok) cout << "re-inserted w/ " << -tmp.se << " " << tmp.fi << " " << i << '\n'; //else cout << "not possible to gain profit anywhere\n"; if (ok) st.push({-tmp.se, {tmp.fi, i}}); } cout << ans << '\n'; } void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } signed main() { ios::sync_with_stdio(false); cout.tie(0); cin.tie(0); //setIO(); int t = 1; if (tc) { cin >> t; } while (t--) { solve(); } }

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:105:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...