Submission #1160470

#TimeUsernameProblemLanguageResultExecution timeMemory
1160470borisAngelovAliens (IOI16_aliens)C++17
12 / 100
31 ms4424 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; const int maxn = 4005; const long long inf = (1LL << 62); int n, m, k; pair<int, int> points[maxn]; vector<pair<int, int>> v; long long dp[maxn][maxn]; long long sq(long long x) { return x * x; } long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) { m = M; k = K; for (int i = 1; i <= N; ++i) { int x = r[i - 1] + 1; int y = c[i - 1] + 1; if (x > y) { swap(x, y); } v.push_back({x, y}); //cout << "add " << x << " " << y << endl; } sort(v.begin(), v.end()); n = 0; for (int i = 0; i < N; ++i) { if (i == 0 || v[i] != v[i - 1]) { points[++n] = v[i]; //cout << "now " << points[i].first << " " << points[i].second << endl; } } for (int i = 0; i <= n; ++i) { for (int j = 0; j <= k; ++j) { dp[i][j] = inf; } } dp[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= min(i, k); ++j) { for (int prv = j; prv <= i; ++prv) { long long cost = sq(points[i].second - points[prv].first + 1); if (prv > 1 && points[prv - 1].second >= points[prv].first) cost -= sq(points[prv - 1].second - points[prv].first + 1); dp[i][j] = min(dp[i][j], dp[prv - 1][j - 1] + cost); } //cout << i << " " << j << " :: " << dp[i][j] << endl; } } long long ans = inf; for (int i = 1; i <= k; ++i) { ans = min(ans, dp[n][i]); } return ans; }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...