#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fo(i,n) for(auto i =0 ; i < n;i++)
#define fore(i,l,r) for(auto i = l; i < r;i++)
#define forex(i,r,l) for(auto i = r; i >= l; i--)
#define ffo(i,n) forex(i,n-1,0)
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define sz(x) (int)x.size()
#define gcd(a,b) __gcd(a,b)
#define vii vector<ii>
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<ll>;using ii = pair<ll,ll>;using mii = map<ll,ll>;
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
const int LOG = 13;
struct fenwick{
vector<ll> ft;int n;
fenwick(int kkk){n=kkk;ft.resize(n+2,0);}
void update(int idx, ll val){for(; idx < n; idx += lsb(idx))ft[idx]+=val;}
ll query(int idx){ll res = 0;for(;idx>0;idx-=lsb(idx))res+=ft[idx];return res;}
ll query(int l, int r ){if(l>r)return 0;return query(r) - query(l-1);}
int lwb(ll v){
ll sum = 0;int pos=0;
for(int i=LOG; i>=0; i--)
if(pos + (1 << i) < n and sum + ft[pos + (1 << i)] < v){
sum += ft[pos + (1 << i)];pos += (1 << i);
}return pos + 1;
}
};
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w){
ll suf[n+1]{}, pre[n+1]{};
fore(i,1,n)pre[i] = (i ? w[i-1] : 0) + (i ? pre[i-1] : 0);
ffo(i,n-1)suf[i] = w[i] + suf[i+1];
ll disx[n+1]{};
for(int i = x-1; i >= 0; i--)disx[i] = disx[i+1] + w[i];
ll disy[n+1]{} , ans = 0;
for(int i = y+1; i <= n-1;i++)disy[i] = disy[i-1] + w[i-1];
int tot = 0;
vi ord;fo(i,x+1)ord.pb(disx[i]);fore(i,y,n)ord.pb(disy[i]);
sort(all(ord)) ;
// for(int v : ord) cout << v << " ";cout<<endl;
for(int j = x; j <= n-1; j++ ){
// cout << "Nuevo indice " << j << endl;
ans+= pre[j] - pre[x];
fenwick cnt(2*n+1), sum(2*n+1);
int last = 0;
for(int l=y;l>=0;l--){
if(l>j)ans+=suf[l]- suf[y];
else{
if(l>x){
if(j>=l){
if(suf[l]-suf[y] > pre[l] - pre[x]){
ans -= pre[l] - pre[x];
ans+=suf[l]-suf[y];
}
}
else ans+= suf[l]-suf[y];
}
else{ans+=suf[l]-suf[y];if(l>=j)ans-=suf[l] - suf[x];}
}
}
for(int i = max(y+1,j+1); i <= n-1; i++){
// disy[i]
// cout << disy[i] << " ";
int pos = lower_bound(all(ord), disy[i])-ord.begin();
// inserto esta, 1-indexado
cnt.update(pos+1, +1);
sum.update(pos+1, +disy[i]);
}
// cout<<endl;
for(int l =0;l<=y;l++){
if(ans <= k){
int lb = 1, rb = cnt.query(1, 2*n);
// cout << "Busqueda binaria " << endl;
while(lb<=rb){
int mid = (lb+rb)/2;
// ahora quiero poner mid nuevos
// cout << lb << " " << rb << " " << mid << endl;
int pos = cnt.lwb(mid);
// cout << "Posicion del ultimo valor que debería poner" << endl;
// cout << pos << endl;
// cout << "Valor" << endl;
// cout << ord[pos-1] << endl;
ll con = sum.query(1, pos-1) + ((mid-cnt.query(1,pos-1))* ord[pos-1]);
// cout << "Lo que me cuesta" << endl;
// cout << con << endl;
if(con+ans <= k) lb = mid+1;
else rb = mid-1;
}
tot = max(tot, j-x+1 + y-l+1 + rb);
}
// cout << ans << " " << j << " " << l << " " << lb << " " << rb << endl;
// for(int idx = 1; idx <= 2*n;idx++)cout << cnt.query(idx,idx) << " ";cout << endl;
// for(int idx = 1; idx <= 2*n; idx ++ )cout << sum.query(idx,idx) << " "; cout << endl;
// cout << endl << endl;
if(l>j)ans-=suf[l]- suf[y];
else{
if(l>x){
if(j>=l){
if(suf[l]-suf[y] > pre[l] - pre[x]){
ans += pre[l] - pre[x];
ans -=suf[l]-suf[y];
}
}
else ans -= suf[l]-suf[y];
}
else{ans-=suf[l]-suf[y];if(l>=j)ans+=suf[l] - suf[x];}
}
// insertar disx[l]
int pos = lower_bound(all(ord), disx[l])-ord.begin();
// inserto esta, 1-indexado
if(l <= x-1){
cnt.update(pos+1, +1);
sum.update(pos+1, +disx[l]);
}
}
}
return tot;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, ll, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:53:13: warning: unused variable 'last' [-Wunused-variable]
53 | int last = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1022 ms |
19028 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
