제출 #204436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
204436		awlintqaa	Aliens (IOI16_aliens)	C++14	0 / 100	6 ms	2456 KiB

aliens

    #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
    #include <bits/stdc++.h>
    using namespace std;
    #define sqr 200
    #define mid (l+r)/2
    #define pb push_back
    #define ppb pop_back
    #define fi first
    #define se second
    #define lb lower_bound
    #define ub upper_bound
    #define ins insert
    #define era erase
    #define C continue
    #define mem(dp,i) memset(dp,i,sizeof(dp))
    #define mset multiset
    typedef long long ll;
    typedef short int si;
    typedef long double ld;
    typedef pair<int,int> pi;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pi> vpi;
    typedef vector<pll> vpll;
    const ll mod=1e9+7;
    const ll inf= 4e18;
    const ld pai=acos(-1);
    #include "aliens.h"
    ll n,m,k;
    vll v;
    ll dp[509][509];
    ll x[509],y[509],MX[509],MN[509];
    pair<pll,pll> calc(ll x,ll y){
            if(x==y)return {{x,x},{y,y}};
            if(x<y){
                    ll X=y-x;
                    return {{x,x+X},{y-X,y}};
            }
            ll X=x-y;
            return {{x-X,x},{y,y+X}};
    }
	bool overflow(ll a,ll b){
      return a > inf/b;
    }
    ll bt(ll id,ll crnt){
            if(id==v.size()){
                    if(crnt>k)return (ll)1e9;
                    return 0;
            }
            ll &ret=dp[id][crnt];
            if(ret!=-1)return ret;
            ret=(ll)1e9;
            ll cost=0;
            ll xmx=0,xmn=inf,ymx=0,ymn=inf;
            for(ll i=id;i<v.size();i++){
                    pair<pll,pll> X=calc(MN[v[i]],v[i]);
                    xmn=min(xmn,X.fi.fi);
                    xmx=max(xmx,X.fi.se);
                    ymn=min(ymn,X.se.fi);
                    ymx=max(ymx,X.se.se);
                    X=calc(MX[v[i]],v[i]);
                    xmn=min(xmn,X.fi.fi);
                    xmx=max(xmx,X.fi.se);
                    ymn=min(ymn,X.se.fi);
                    ymx=max(ymx,X.se.se);
                    ll sz= min( xmx - xmn , ymx - ymn )+1;
              		if ( overflow(sz,sz))break;
                    ret=min(ret,bt(i+1,crnt+1) + sz*sz );
            }
            return ret;
    }
    ll take_photos(int N, int M, int K, vi r, vi c) {
            mem(dp,-1);
            n=N,k=K,m=M;
            set<ll>s;
            for(int i=0;i<n;i++){
                    x[i]=r[i];
                    y[i]=c[i];
                    s.ins(y[i]);
                    MN[y[i]]=inf;
            }
            for(int i=0;i<n;i++){
                    MX[y[i]]=max(MX[y[i]],x[i]);
                    MN[y[i]]=min(MN[y[i]],x[i]);
            }
            for(auto u:s)v.pb(u);
            return bt(0,0);
    }

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

aliens.cpp: In function 'll bt(ll, ll)':
aliens.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(id==v.size()){
                ~~^~~~~~~~~~
aliens.cpp:56:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(ll i=id;i<v.size();i++){
                         ~^~~~~~~~~
aliens.cpp:54:16: warning: unused variable 'cost' [-Wunused-variable]
             ll cost=0;
                ^~~~

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