제출 #571002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571002		definitelynotmee	Aliens (IOI16_aliens)	C++98	0 / 100	1 ms	212 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<= 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);
        };
    }
    return dp[n-1];
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:44:14: warning: variable 'dc' set but not used [-Wunused-but-set-variable]
   44 |         auto dc =[&](int l, int r, int optl, int optr, auto dc)->void{
      |              ^~

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