Submission #67171

#	Time	Username	Problem	Language	Result	Execution time	Memory
67171		Talant	Aliens (IOI16_aliens)	C++17	12 / 100	158 ms	4596 KiB

aliens

#include "aliens.h"
//#include "grader.cpp"

#include <bits/stdc++.h>

#define mk make_pair
#define sc second
#define fr first
#define pb push_back

using namespace std;

const int N = (1e6 + 5);
const int inf = (1e9 + 7);

pair<int,int> dp[1005][1005];
int a[1005][1005];
int cn = 0;
int u[N];
int mn;
int ans = inf;

vector <int> v;

int f (int mn,int i,int j,int k) {
      if (mn > v[j]) return 0;
      return ((v[j] - max(mn,dp[j][k - 1].sc) + 1) * (v[j] - max(mn,dp[j][k - 1].sc) + 1));
}
long long take_photos(int n, int m, int kk, vector<int> r, vector<int> c) {
      for (int i = 0; i < m; i ++) u[i] = -1;

      for (int i = 0; i < n; i ++) {
            if (u[max(r[i],c[i])] == -1) v.pb(max(r[i],c[i])),u[max(r[i],c[i])] = min(r[i],c[i]);
            else u[max(r[i],c[i])] = min(u[max(r[i],c[i])],min(r[i],c[i]));
      }
      sort (v.begin(),v.end());

      for (int i = 0; i < v.size(); i ++)
            for (int k = 1; k <= kk; k ++)
                  dp[i][k].fr = dp[i][k].sc = inf;

      mn = u[v[0]];
      for (int i = 0; i < v.size(); i ++) {
            mn = min(mn,u[v[i]]);
            dp[i][1].fr = (v[i] - mn + 1) * (v[i] - mn + 1);
            dp[i][1].sc = mn;
      }

      for (int k = 2; k <= kk; k ++) {
            for (int i = 0; i < v.size(); i ++) {
                  mn = u[v[i]];
                  for (int j = i - 1; j >= 0; j --) {
                        if (dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k) < dp[i][k].fr)
                              dp[i][k].fr = dp[j][k - 1].fr + (v[i] - mn + 1) * (v[i] - mn + 1) - f(mn,i,j,k),dp[i][k].sc = mn;

                        mn = min(mn,u[v[j]]);
                  }
            }
      }
      for (int i = 1; i <= kk; i ++)
            ans = min(ans,dp[(int)v.size() - 1][i].fr);

      return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:38:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < v.size(); i ++)
                       ~~^~~~~~~~~~
aliens.cpp:43:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < v.size(); i ++) {
                       ~~^~~~~~~~~~
aliens.cpp:50:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < v.size(); i ++) {
                             ~~^~~~~~~~~~

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