Submission #593194

#	Time	Username	Problem	Language	Result	Execution time	Memory
593194		Koosha_mv	Aliens (IOI16_aliens)	C++14	25 / 100	8 ms	724 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=50500,K=111;
const ll inf=1e15;

int n,m,k,ans,A[N],B[N],rem[N];
ll dp[N][K];

ll cost(int i,int j){
    ll res=B[j]-A[i]+1;
    return res*res;
}
ll G(int x){
    if(x==1) return 0;
    ll res=B[x-1]-A[x]+1;
    if(res<=0) return 0;
    return res*res;
}
void solve(int l,int r,int s,int e,int x){
    if(r<=l) return ;
    //cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<x<<endl;
    int mid=(l+r)>>1,p=s;
    f(i,s,min(e,mid+1)){
        if(dp[i-1][x-1]+cost(i,mid)-G(i)<dp[mid][x]){
            dp[mid][x]=dp[i-1][x-1]+cost(i,mid)-G(i);
            p=i;
        }
    }
    solve(l,mid,s,p+1,x);
    solve(mid+1,r,p,e,x);
}
void edame(){
    minm(k,n);
    f(i,1,n+1) f(j,0,k+1) dp[i][j]=inf;
    f(i,1,k+1){
        solve(1,n+1,1,n+1,i);
        //cout<<i<<" -> "<<endl;
        //cout<<"dp : ";
        //f(j,1,n+1) cout<<dp[j][i]<<" ";
        //cout<<endl;
    }
    ans=dp[n][k];
}
ll take_photos(int _n,int _m,int _k,vector<int> r,vector<int> c) {
    n=_n,m=_m,k=_k;
    f(i,0,n) if(r[i]>c[i]) swap(r[i],c[i]);
    vector<int> vec(n);
    iota(all(vec),0);
    sort(all(vec),[&](int u,int v){ return r[u]+c[u]<r[v]+c[v]; });
    int mx=-1,mn=m+1;
    f(i,0,vec.size()){
        if(mx>c[vec[i]]) rem[i]=1;
        maxm(mx,c[vec[i]]);
    }
    f_(i,vec.size()-1,0){
        if(mn<r[vec[i]]) rem[i]=1;
        minm(mn,r[vec[i]]);
    }
    n=0;
    f(i,0,vec.size()){
        if(rem[i]) continue ;
        n++;
        A[n]=r[vec[i]];
        B[n]=c[vec[i]];
    }
    edame();
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   72 |     f(i,0,vec.size()){
      |       ~~~~~~~~~~~~~~           
aliens.cpp:72:5: note: in expansion of macro 'f'
   72 |     f(i,0,vec.size()){
      |     ^
aliens.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   81 |     f(i,0,vec.size()){
      |       ~~~~~~~~~~~~~~           
aliens.cpp:81:5: note: in expansion of macro 'f'
   81 |     f(i,0,vec.size()){
      |     ^

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