#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;
const ll inf=1e18*4;
const ld pai=acos(-1);
ll m,n,sum;
vll f;
ll st[500009];
set<pair<pi,ll> > s1;
set<pair<pi,ll> > s2;
vector<pair<pi,ll> >v;
int main(){
fast;
mem(st,-1);
cin>>m>>n;
for(int i=0;i<n;i++){
ll a,b;cin>>a>>b;
s2.ins({{a,b},i});
}
while(s1.size()<6){
s1.ins(*s2.rbegin());
st[s2.rbegin()->se]=1;
f.pb(s2.rbegin()->se);
s2.era(*s2.rbegin());
}
ll M=1;
while(M<=m){
vector<pair<pi,ll> >ret;
for(auto i=s1.begin();i!=s1.end();i++){
sum+=i->fi.fi;
if(M-st[i->se]+1==i->fi.se)ret.pb(*i);
}
if(M<m){
for(auto u:ret){
s1.era(u);
s1.ins(*s2.rbegin());
st[s2.rbegin()->se]=M+1;
v.pb({{M,u.se},s2.rbegin()->se});
s2.era(*s2.rbegin());
}
}
M++;
}
cout<<sum<<endl;
for(auto u:f)cout<<u+1<<" ";
cout<<endl;
cout<<v.size()<<endl;
for(auto u:v){
cout<<u.fi.fi<<" "<<u.fi.se+1<<" "<<u.se+1<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4216 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4600 KB |
Output is correct |
| 3 |
Correct |
37 ms |
5880 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
4344 KB |
Output isn't correct |
| 5 |
Correct |
21 ms |
4984 KB |
Output is correct |
| 6 |
Incorrect |
10 ms |
4472 KB |
Output isn't correct |
| 7 |
Incorrect |
10 ms |
4856 KB |
Output isn't correct |
| 8 |
Incorrect |
118 ms |
10956 KB |
Output isn't correct |
| 9 |
Incorrect |
623 ms |
40572 KB |
Output isn't correct |
| 10 |
Incorrect |
670 ms |
36052 KB |
Output isn't correct |
