Submission #237208

#TimeUsernameProblemLanguageResultExecution timeMemory
237208MlxaHokej (COCI17_hokej)C++14
120 / 120
196 ms12792 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll #define all(x) x.begin(), x.end() #define x first #define y second #define mp make_pair #define mt make_tuple const int N = 1e6; struct pl { int val; int len; int ind; pl(int a = 0, int b = 0, int c = 0) : val(a), len(b), ind(c) {} }; bool byval(pl a, pl b) { return a.val > b.val; } bool bylen(pl a, pl b) { return a.len > b.len; } int n; int m; int fir[6]; vector<pl> srt; vector<tuple<int, int, int>> rec; signed main() { #ifdef LC assert(freopen("input.txt", "r", stdin)); #endif ios::sync_with_stdio(0); cin.tie(0); cin >> m >> n; srt.resize(n); int sum = 0; for (int i = 0; i < n; ++i) { cin >> srt[i].val >> srt[i].len; srt[i].ind = i + 1; } sort(all(srt), byval); vector<pl> cut; int need = 6 * m; for (auto e : srt) { if (sum >= need) { break; } int cur = min(need - sum, e.len); e.len = min(e.len, cur); sum += cur; cut.push_back(e); } srt = cut; sort(all(srt), bylen); int ans = 0; int row = 0; int tim = 0; int lst = -1; for (auto e : srt) { if (lst != -1 && 0 < tim && tim < m) { rec.emplace_back(tim, lst, e.ind); } lst = e.ind; int least = e.len; while (row < 6 && least > 0) { int dur = min(least, m - tim); ans += dur * e.val; least -= dur; if (!fir[row]) { fir[row] = e.ind; } tim += dur; if (tim == m) { tim = 0; ++row; } } } sort(all(rec)); cout << ans << "\n"; for (int i = 0; i < 6; ++i) { cout << fir[i] << " "; } cout << "\n"; cout << rec.size() << "\n"; for (auto e : rec) { cout << get<0>(e) << " " << get<1>(e) << " " << get<2>(e) << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...