Submission #291218

#	Time	Username	Problem	Language	Result	Execution time	Memory
291218		peti1234	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	384 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=0, e=sz[i].first, h=0;
        for (int k=0; k<i; k++) maxi=max(maxi, sz[k].second);
        maxi=max(0, maxi-e);
        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+1][j]+(h-e)*(h-e)-maxi*maxi);
        }
    }
    return dp[n][t];
}

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