# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
79853 | pzdba | Hokej (COCI17_hokej) | C++14 | 180 ms | 10704 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<pii, int> piipi;
int k[500005], l[500005];
piipi p[500005];
vector<int> ans1;
vector<piipi> ans2;
int main(){
int m, n;
scanf("%d%d", &m, &n);
for(int i=1;i<=n;i++){
scanf("%d%d", &k[i], &l[i]);
p[i] = piipi(pii(-k[i], l[i]), i);
}
sort(p+1, p+1+n);
LL ans = 0;
int cur = 1, tot = 0, pv = -1;
for(int i=1;i<=n;i++){
int idx = p[i].second;
if(tot == 0) ans1.emplace_back(idx);
else if(pv != -1 && tot != m) ans2.emplace_back(piipi(pii(tot, pv), idx));
if(tot+l[idx] <= m){
tot += l[idx];
ans += (LL)l[idx]*k[idx];
if(tot == m){
cur++;
tot = 0;
if(cur > 6) break;
}
}
else{
ans += (LL)(m-tot)*k[idx];
l[idx] = l[idx] - (m-tot);
i--;
cur++;
tot = 0;
if(cur > 6) break;
}
pv = idx;
}
printf("%lld\n", ans);
for(int i=0;i<ans1.size();i++) printf("%d ", ans1[i]);
printf("\n");
sort(ans2.begin(), ans2.end());
printf("%d\n", ans2.size());
for(int i=0;i<ans2.size();i++) printf("%d %d %d\n", ans2[i].first.first, ans2[i].first.second, ans2[i].second);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |