Submission #593134

#	Time	Username	Problem	Language	Result	Execution time	Memory
593134		FatihSolak	Aliens (IOI16_aliens)	C++17	25 / 100	2082 ms	4308 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);
    
}
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;
        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];
            //cout << dp[i] << " ";
        }
        //cout << endl;
        ans = min(ans,dp[n]);
    }
    return ans;
}

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