Submission #291233

#	Time	Username	Problem	Language	Result	Execution time	Memory
291233		peti1234	Aliens (IOI16_aliens)	C++17	25 / 100	253 ms	4736 KiB

aliens

#include <bits/stdc++.h>

using namespace std;
const int c=502;
long long dp[c][c];
vector<pair<int, int> > sz;
long long take_photos(int n, int m, int t, vector<int> x, vector<int> y) {
    for (int i=0; i<n; i++) {
        int a=min(x[i], y[i]), b=max(x[i], y[i]);
        sz.push_back({a, b});
    }
    sort(sz.begin(), sz.end());
    for (int i=1; i<=n; i++) for (int j=0; j<=t; j++) dp[i][j]=1e9;
    for (int i=0; i<n; i++) for (int j=0; j<t; j++) {
        int maxi=-1, e=sz[i].first, h=0;
        for (int k=0; k<i; k++) maxi=max(maxi, sz[k].second);
        maxi=max(0, maxi-e+1);
        for (int k=i; k<n; k++) {
            h=max(h, sz[k].second);
            if (h>=maxi+e) dp[k+1][j+1]=min(dp[k+1][j+1], dp[i][j]+(h-e+1)*(h-e+1)-maxi*maxi);
            //cout << "dp " << i << " " << k+1 << " " << j+1 << " " << dp[k+1][j+1] << "\n";
        }
    }
    return dp[n][t];
}

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