Submission #21726

#	Time	Username	Problem	Language	Result	Execution time	Memory
21726		sbansalcs	Aliens (IOI16_aliens)	C++14	4 / 100	0 ms	3584 KiB

aliens

#include "aliens.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
// typedef pair<int,int> line;

const int N = 100005;
const ll inf=1e16;
// int arr[M];
// int vis[M];
// int cost[N][N];
vector<pair<int,int>> vtx;
vector<pair<int,int>> vt;

int n2;
ll dp[2][N];


struct line 	{
    ll m,c;
    int taken;
    line()	{
        taken=0;
    }
    line(ll _m,ll _c, int _taken)	{
        m=_m,c=_c,taken=_taken;
    }
    ll val(ll x)	{
        return m*x+c;
    }
    
};



struct ConvexHull	{
    vector<line> lines;
    int curr=0;
    bool isBad(line l1,line l2,line l3)	{
        return (l3.c-l1.c)*(l2.m-l3.m) <= (l1.m-l3.m)*(l3.c-l2.c);
    }
    
    void insert(line l)	{
        int sz=lines.size();
        while(sz>=2 && isBad(lines[sz-2], lines[sz-1],l))	{
            lines.erase(lines.end()-1);
            sz--;
        }
        lines.push_back(l);
    }
    ll query(ll x)	{
        if(curr>=lines.size())	curr=lines.size()-1;
        while(curr<lines.size()-1 && lines[curr].val(x)<=lines[curr+1].val(x))	curr++;
        return lines[curr].val(x);
    }
    ll queryT() {
        return lines[curr].taken;
    }
};





bool cmp(pair<int,int> a, pair<int,int> b)	{
    if(a.first==b.first)	return a.second>b.second;
    return a.first<b.first;
}

ll solve(int n, ll cost, int bit)  {
    dp[bit][0]=0;
    int tak=0;
    ConvexHull hull;
    for (int i=0; i<=n; i++) {
//        cout<<"hoo: "<<i<<endl;
        if(i==0)    {
            hull.insert(line(vt[i].f,cost-1LL*(vt[i].f)*(vt[i].f)+2*(vt[i].f),tak));
        }
        else	{
            dp[bit][i]=hull.query(2*vt[i-1].s);
            dp[bit][i]*=-1;
            dp[bit][i]+=1LL*(vt[i-1].s)*(vt[i-1].s)+1LL*2*(vt[i-1].s);
            dp[bit][i]++;
            tak=hull.queryT();tak++;
            ll g=max(0,vt[i-1].s-vt[i].f+1);g*=g;
            hull.insert(line(vt[i].f,g+cost-dp[!bit][i]-1LL*(vt[i].f)*(vt[i].f)+2*(vt[i].f),tak));
//            cout<<i<<" : "<<dp[bit][i]<<endl;
        }
        
    }
    return tak;
}


ll cost(int i, int j)	{
    i--,j--;
    ll f=vt[j].second-vt[i].first+1;f*=f;
    if(i==0)	return f;
    ll g=max(0,vt[i-1].second-vt[i].first+1);g*=g;
    return f-g;
}
//
//void pro(int a, int b, int start, int end, int x)	{
//    if(b<a)	return;
//    int mid=(a+b)/2;
//    int ind=start;
//    ll ans=cost(start,mid)+dp[!x][start-1],h;
//    for(int i=ind+1;i<=end && i<=mid;i++)	{
//        h=cost(i,mid)+dp[!x][i-1];
//        if(h<ans)	{
//            ans=h;ind=i;
//        }
//    }
//    dp[x][mid]=ans;
//    pro(a,mid-1,start,ind,x);
//    pro(mid+1,b,ind,end,x);
//}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    
    
    for(int i=0;i<n;i++)	{
        vtx.push_back({min(r[i],c[i]), max(r[i],c[i])});
    }
    sort(vtx.begin(),vtx.end(),cmp);
    int s;
    for(auto c:vtx)	{
        s=vt.size();s--;
        if(s!=-1 && c.second<=vt[s].second)	continue;
        vt.push_back(c);
//        cout<<c.first<<" , "<<c.second<<endl;
    }
    
    int n2=vt.size();
    
    // for(int i=0;i<n;i++)	{
    // 	if(vt2[i]>vt1[i])	{
    // 		swap(vt2[i],vt1[i]);
    // 	}
    // 	if(vis[vt1[i]])	arr[vt1[i]]=min(arr[vt1[i]],vt2[i]);
    // 	else	{
    // 		arr[vt1[i]]=vt2[i];
    // 		vis[vt1[i]]=1;
    // 		vt.push_back(vt1[i]);
    // 	}
    // }
    
    
    // sort(vt.begin(),vt.end());
    // int n2=vt.size();
    // ll g;
    // for(int i=0;i<n2;i++)	{
    // cout<<i<<" : "<<vt[i]<<" , "<<arr[vt[i]]<<endl;
    
    // }
    
    // for(int i=0;i<n2;i++)	{
    // 	int s=1e7;
    // 	for(int j=i;j<n2;j++)	{
    // 		s=min(arr[vt[j]],s);
    // 		cost[i][j]=1+vt[j]-s;cost[i][j]*=cost[i][j];
    // 		cout<<i<<"  "<<j<<" : "<<cost[i][j]<<endl;
    // 	}
    // }
    
    // for(int i=0;i<n2;i++)	{
    // 	for(int j=1;j<=i+1 && j<=k;j++)	{
    // 		if(j==1)
    // 	}
    // }
    
    
    
    //    int a,b;
    //
    //
    //    for(int i=0;i<=k;i++)	{
    //        a=i&1;b=a^1;
    //        dp[a][0]=0;
    //        if(i==0)	{
    //            for(int j=1;j<=n2;j++)	{
    //                dp[a][j]=inf;
    //            }
    //        }
    //        else	{
    //            pro(1,n2,1,n2,a);
    //        }
    //        // for(int j=0;j<=n;j++)	{
    //        // 	if(j==0)	dp[a][j]=0;
    //        // 	else	{
    //
    //        // 	}
    //        // }
    //    }
    
    // for(int i=0;i<=k;i++)	{
    // 	a=i&1;b=a^1;
    // 	for(int j=0;j<n2;j++)	{
    // 		dp[a][j]=inf;
    // 		s=1e7;
    // 		if(i!=0)	dp[a][j]=min(dp[a][j],dp[b][j]);
    // 		if(i!=0 && i<=j+1)	{
    
    // 		for(int l=j;l>=0;l--)	{
    
    // 			f=vt[j].second-vt[l].first+1;f*=f;
    // 			if(l==0)	{
    // 					dp[a][j]=min(dp[a][j],f);
    // 			}
    // 			else	{
    // 				g=max(0,vt[l-1].second-vt[l].first+1);g*=g;
    // 				dp[a][j]=min(dp[a][j],dp[b][l-1]+f-g);
    // 			}
    // 		}
    // 	}
    // 		// cout<<i<<"  "<<j<<" : "<<dp[a][j]<<endl;
    // 	}
    // }
    for (int i=1; i<=k; i++) {
//        cout<<"do: "<<i<<endl;
        if(i==1)    {
            for(int j=1;j<=n2;j++)   {
                dp[i&1][j]=cost(1, j);
//                cout<<j<<"  "<<dp[i&1][j]<<endl;
            }
        }
        else    {
            solve(n2, 0, i&1);
        }
//        cout<<endl<<endl;
    }
//    cout<<"done\n";
    
    return dp[k&1][n2];
    //    return 0;
}

Compilation message (stderr)

aliens.cpp: In member function 'll ConvexHull::query(ll)':
aliens.cpp:57:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(curr>=lines.size()) curr=lines.size()-1;
                ^
aliens.cpp:58:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(curr<lines.size()-1 && lines[curr].val(x)<=lines[curr+1].val(x)) curr++;
                   ^

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