Submission #1041115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041115		vjudge1	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	348 KiB

aliens

#include "aliens.h"

#include<bits/stdc++.h>
using namespace std;

using lint=int64_t;
using pii=pair<lint,lint>;

#define pb push_back


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++){
        if(c[i]<r[i]){
            swap(c[i],r[i]);
        }
    }
    int points[m+1];
    memset(points,-1,sizeof(points));
    for(int i=0;i<n;i++){
        points[r[i]]=max(points[r[i]],c[i]);
    }
    vector<pii>pts;
    for(int i=0;i<=m;i++){
        if(points[i]!=-1){
            if(!pts.size()||pts.back().second<points[i]){
                pts.pb(pii{i,points[i]});
            }
        }
    }
    n=pts.size();
    lint ans[n][k+1];
    ans[0][1]=(pts[0].second-pts[0].first+1)*(pts[0].second-pts[0].first+1);
    for(int i=1;i<n;i++){
        //cerr<<i<<"\n";
        ans[i][2]=(pts[i-1].second-pts[0].first+1)*(pts[i-1].second-pts[0].first+1)
            +(pts[i].second-pts[i].first+1)*(pts[i].second-pts[i].first+1);
        if(pts[i].first<=pts[i-1].second){
            ans[i][2]-=(pts[i-1].second-pts[i].first+1)*(pts[i-1].second-pts[i].first+1);
        }
        for(int j=3;j<=min(i+1,k);j++){
            ans[i][j]=LLONG_MAX;
            for(int past=j-2;past<i;past++){
                //cerr<<past<<" "<<j-1<<" "<<ans[past][j-1]<<" wha\n";
                lint aa=ans[past][j-1]+(pts[i].second-pts[i].first+1)*(pts[i].second-pts[i].first+1);
                //cerr<<aa<<"\n";
                if(pts[i].first<=pts[past].second){
                    aa-=(pts[past].second-pts[i].first+1)*(pts[past].second-pts[i].first+1);
                }
                //cerr<<aa<<"\n";
                ans[i][j]=min(ans[i][j],aa);
            }
        }
        /*
       cerr<<"debug\n";
        for(int j=2;j<=k;j++){
            cerr<<ans[i][j]<<" ";
        }
        cerr<<"\n";
        */
    }
    //cerr<<b[0]<<"\n";
    //cerr<<n<<"\n";
    lint anss=LLONG_MAX;
    for(int i=1;i<=min(k,n);i++){
        if(i==1&&n!=1)continue;
        anss=min(anss,ans[n-1][i]);
    }
    //cerr<<LLONG_MAX<<"\n";
    //cerr<<anss<<"\n";
    int i=n-1;
    for(int j=1;j<=min(i+1,k);j++){
        for(int past=j-1;past<i;past++){
            if(j==1&&past)break;
            lint cur=ans[past][j]
                +(pts[i].second-pts[past].first+1)*(pts[i].second-pts[past].first+1)
                -(pts[past].second-pts[past].first+1)*(pts[past].second-pts[past].first+1);
            anss=min(anss,cur);
        }
    }
    return anss;
}

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