답안 #979975

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
979975 2024-05-11T18:13:32 Z vjudge1 봉쇄 시간 (IOI23_closing) C++17
0 / 100
1000 ms 19608 KB
#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 = 10;
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){
    // 14 > 5 + 6
    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;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 = 0, 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:54:13: warning: unused variable 'last' [-Wunused-variable]
   54 |         int last = 0;
      |             ^~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1073 ms 19608 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -