#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
ll a[100005], b[100005], toa[100005], tob[100005];
struct num
{
ll t, i, j;
num(){}
num(ll i, ll t): i(i), t(t)
{
if (t==0) j=toa[i];
else j=tob[i];
}
bool operator < (const num &o) const
{
ll v=t==0?a[i]-a[j]:b[i]-b[j], ov=o.t==0?a[o.i]-a[o.j]:b[o.i]-b[o.j];
return v*(o.j-o.i)<ov*(j-i);
}
};
set <num> S;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, m, cn, cm, ans=0; cin >> n >> m; cn=n, cm=m;
for (ll i=1; i<=n; i++) cin >> a[i];
for (ll i=1; i<=m; i++) cin >> b[i];
for (ll i=1; i<n; i++) toa[i]=i+1, S.insert(num(i, 0));
for (ll i=1; i<m; i++) tob[i]=i+1, S.insert(num(i, 1));
while (S.size())
{
num Min=*S.begin(); S.erase(S.begin());
ll t=Min.t, i=Min.i, j=Min.j;
if (t==0)
{
if (j==cn) ans+=b[cm]*(j-i), cn=i;
else
{
S.erase(num(j, 0)), toa[i]=toa[j];
S.insert(num(i, 0));
}
}
else
{
if (j==cm) ans+=a[cn]*(j-i), cm=i;
else
{
S.erase(num(j, 1)), tob[i]=tob[j];
S.insert(num(i, 1));
}
}
}
cout << ans << "\n";
}
Compilation message
kyoto.cpp: In constructor 'num::num(long long int, long long int)':
kyoto.cpp:14:11: warning: 'num::i' will be initialized after [-Wreorder]
14 | ll t, i, j;
| ^
kyoto.cpp:14:8: warning: 'long long int num::t' [-Wreorder]
14 | ll t, i, j;
| ^
kyoto.cpp:16:5: warning: when initialized here [-Wreorder]
16 | num(ll i, ll t): i(i), t(t)
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2532 KB |
Output is correct |
10 |
Correct |
2 ms |
2648 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
2 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2652 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Incorrect |
1 ms |
2556 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
2 ms |
2532 KB |
Output is correct |
10 |
Correct |
2 ms |
2648 KB |
Output is correct |
11 |
Correct |
2 ms |
2652 KB |
Output is correct |
12 |
Correct |
2 ms |
2652 KB |
Output is correct |
13 |
Correct |
1 ms |
2652 KB |
Output is correct |
14 |
Correct |
2 ms |
2652 KB |
Output is correct |
15 |
Correct |
2 ms |
2652 KB |
Output is correct |
16 |
Incorrect |
1 ms |
2556 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |