#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
#define MP make_pair
#define fi first
#define se second
#define pll pair <ll,ll>
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i))
ll n,m;
const ll MAXN = 1e5+100;
vector <pll> all[MAXN];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n=N,m=M;
ll bot1,bot2,top;
bot1 = bot2 = top = 0;
map <ll,ll> mp1,mp2;
ll sum1=0,sum2=0;
mp1[0] = mp2[0] = 0;
for (ll i = 0;i < m;i ++){
all[X[i]].push_back(MP(Y[i],W[i]));
}
for (ll i = 0;i < n;i ++)sort(all[i].begin(),all[i].end());
for (ll i = 1;i < n;i ++){
// cout<<i<<endl;
while ((*mp1.begin()).se<bot2){
ll x = (*mp1.begin()).se;
sum1 -= x;
mp1.erase(mp1.begin());
if (!mp1.empty()){
(*mp1.begin()).se += x;
sum1 += x;
}
else break;
}
if (!mp1.empty())(*mp1.begin()).se -= bot2;
else sum1 = bot2;
mp1[-1] = bot2;
for (auto x:all[i-1]){
mp1[x.fi] -= x.se;
sum1 -= x.se;
auto cur = mp1.find(x.fi);
while ((*cur).se < 0){
ll z = (*cur).se;
cur = mp1.erase(cur);
sum1 -= z;
if (cur==mp1.end())break;
(*cur).se+=z;
sum1 += z;
}
}
// cout<<i<<endl;
for (auto x:all[i-1]){
mp1[x.fi] += x.se;
sum1 += x.se;
}
mp1.erase(mp1.begin());
mp1[0] += bot2;
mp2[n-1] = top - sum2;
sum2 = top;
auto sus = [&](auto tmp){
while ((*tmp).se > 0){
if (tmp==mp2.begin())break;
auto pre = prev(tmp);
(*pre).se += (*tmp).se;
mp2.erase(tmp);
tmp = pre;
}
};
sus(mp2.find(n-1));
for (auto x:all[i]){
mp2[x.fi]+=x.se;
sus(mp2.find(x.fi));
}
// cout<<"OK"<<endl;
// return 0;
ll nw_bot1 = mp2[0];
for (auto x:all[i]){
mp2[x.fi]-=x.se;
}
sum2 -= mp2[n-1];
mp2.erase(mp2.find(n-1));
top = max({top,bot1,sum1});
bot2 = bot1;
bot1 = nw_bot1;
// cout<<endl;
// cout<<bot1<<' '<<bot2<<' '<<top<<endl;
// cout<<"MP1\n";
// for (auto x:mp1)cout<<x.fi<<' '<<x.se<<'\n';
// cout<<"MP2\n";
// for (auto x:mp2)cout<<x.fi<<' '<<x.se<<'\n';
}
return max({bot1,bot2,top});
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
10448 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '709728670' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Incorrect |
120 ms |
18276 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '1909779926' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2648 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
6668 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '2147479351' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2792 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
2652 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '1555350923' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2792 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
2652 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '1555350923' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2792 KB |
Output is correct |
| 9 |
Incorrect |
1 ms |
2652 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '1555350923' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
9 ms |
2648 KB |
Output is correct |
| 3 |
Incorrect |
20 ms |
6668 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '2147479351' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
10448 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '709728670' |
| 2 |
Halted |
0 ms |
0 KB |
- |
