제출 #593142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
593142		FatihSolak	Aliens (IOI16_aliens)	C++17	60 / 100	277 ms	7336 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define N 50005
#define M 1000005
using namespace std;
int maxi[M];
int x[N],y[N];
long long dp[N];
long long ndp[N];
long long calc_len(long long a,long long b,long long c,long long d){
    if(a > c || b > d)return 0;
    return (c - a + 1) * (d - b + 1);
}
long long calc_intersection(long long a0,long long b0,long long c0,long long d0, long long a1,long long b1,long long c1,long long d1){
    long long a2 = max(a0,a1);
    long long b2 = max(b0,b1);
    long long c2 = min(c0,c1);
    long long d2 = min(d0,d1);
    return calc_len(a2,b2,c2,d2);
    
}
void solve(int l,int r,int optl,int optr){
    if(l > r)return;
    int m = (l + r)/2;
    int opt = -1;
    for(int i = optl;i<=min(m,optr);i++){
        if(ndp[m] > dp[i-1] + calc_len(x[i],x[i],y[m],y[m]) - calc_intersection(x[i],x[i],y[m],y[m], x[i-1],x[i-1],y[i-1],y[i-1])){
            opt = i;
            ndp[m] = dp[i-1] + calc_len(x[i],x[i],y[m],y[m]) - calc_intersection(x[i],x[i],y[m],y[m], x[i-1],x[i-1],y[i-1],y[i-1]);
        }
    }
    solve(l,m-1,optl,opt);
    solve(m+1,r,opt,optr);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    for(int i = 0;i<m;i++){
        maxi[i] = -1;
    }
    for(int i = 0;i<n;i++){
        if(r[i] > c[i])swap(r[i],c[i]);
        maxi[r[i]] = max(maxi[r[i]],c[i]);
    }
    vector<pair<int,int>> points;
    for(int i = 0;i<m;i++){
        if(maxi[i] == -1)continue;
        if(points.empty() || maxi[i] > points.back().second){
            points.push_back({i,maxi[i]});
        }
    }
    n = points.size();
    for(int i = 1;i<=n;i++){
        x[i] = points[i-1].first + 1;
        y[i] = points[i-1].second + 1;
        //cout << i << "aaa "<< x[i] << " " << y[i] << endl;
    }
    for(int i = 0;i<=n;i++){
        dp[i] = 2e18;
    }
    dp[0] = 0;
    long long ans = 2e18;
    for(int used = 1;used<=k;used++){
        for(int i = 0;i<=n;i++){
            ndp[i] = 2e18; 
        }
        ndp[0] = 0;
        solve(1,n,1,n);
        /*
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=i;j++){
                ndp[i] = min(ndp[i], dp[j-1] + calc_len(x[j],x[j],y[i],y[i]) - calc_intersection(x[j],x[j],y[i],y[i], x[j-1],x[j-1],y[j-1],y[j-1])     );
            }
        }*/
        for(int i = 0;i<=n;i++){
            dp[i] = ndp[i];
        }
        ans = min(ans,dp[n]);
    }
    return ans;
}

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