Submission #67175

#	Time	Username	Problem	Language	Result	Execution time	Memory
67175		Talant	Aliens (IOI16_aliens)	C++17	25 / 100	267 ms	24832 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 long long N = (1e6 + 5);
const long long inf = (1e9 + 7);

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

vector <long long> v;

long long f (long long mn,long long i,long long j,long long 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 (long long i = 0; i < m; i ++) u[i] = -1;

      for (long long 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])],(long long)min(r[i],c[i]));
      }
      sort (v.begin(),v.end());

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

      mn = u[v[0]];
      for (long long 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 = u[v[i]];
      }

      for (long long k = 2; k <= kk; k ++) {
            for (long long i = 0; i < v.size(); i ++) {
                  mn = u[v[i]];
                  for (long long 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 (long long i = 1; i <= kk; i ++)
            ans = min(ans,dp[(long long)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:39:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (long long i = 0; i < v.size(); i ++)
                             ~~^~~~~~~~~~
aliens.cpp:44:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (long long i = 0; i < v.size(); i ++) {
                             ~~^~~~~~~~~~
aliens.cpp:51:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (long long i = 0; i < v.size(); i ++) {
                                   ~~^~~~~~~~~~

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