Submission #969918

#	Time	Username	Problem	Language	Result	Execution time	Memory
969918		definitelynotmee	Aliens (IOI16_aliens)	C++17	60 / 100	2032 ms	7884 KiB

aliens

    #include<bits/stdc++.h>
    using namespace std;
    #define ff first
    #define ss second
    #define all(x) x.begin(),x.end()
    using ll = long long;
    using pii = pair<int,int> ;
    using pll = pair<ll,ll>;
    template<typename T>
    using matrix = vector<vector<T>>;
    const int INF =(1<<30)-1;
    const ll INFL = (1ll<<61)-1;
     
    long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
     
        vector<pll> v(n);
        for(int i = 0; i < n; i++){
            v[i] = {r[i],c[i]};
            if(r[i]-c[i] > 0){
                swap(v[i].ff,v[i].ss);
            }
        }
     
        vector<pll> pareto{{-1,-1}};
        sort(all(v),[&](pll a, pll b){
            if(a.ff == b.ff)
                return a.ss > b.ss;
            return a.ff < b.ff;
        });
     
        for(int i = 0; i < n; i++){
            if(pareto.back().ss < v[i].ss)
                pareto.push_back(v[i]);
        }
        n = pareto.size();
        swap(v,pareto);
     
        vector<ll> dp(n,INFL);
        dp[0] = 0;
     
     
        while(k--){
            vector<ll> newdp = dp;
            auto dc =[&](int l, int r, int optl, int optr, auto dc)->void{
                if(l > r)
                    return;
                int m = (l+r)>>1;
                pll resp ={INFL,optl};
                for(int l = optl; l<= min(optr,m); l++){
                    ll newarea = (v[m].ss-v[l].ff+1)*(v[m].ss-v[l].ff+1);
                    if(v[l].ff <= v[l-1].ss){
                        newarea-=(v[l-1].ss-v[l].ff+1)*(v[l-1].ss-v[l].ff+1);
                    }
                    resp = min(resp,{dp[l-1]+newarea,l});
                }
                newdp[m] = min(newdp[m],resp.ff);
                dc(l,m-1,optl,resp.ss,dc);
                dc(m+1,r,resp.ss,optr,dc);
            };
            dc(1,n-1,1,n-1,dc);
            swap(dp,newdp);
        }
        return dp[n-1];
    }

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40