Submission #1248278

#TimeUsernameProblemLanguageResultExecution timeMemory
1248278julia_08Aliens (IOI16_aliens)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include "aliens.h" using ll = long long; using namespace std; const int MAXN = 510; ll dp[MAXN][MAXN], inter[MAXN]; ll take_photos(int n, int m, int K, vector<int> l, vector<int> r){ vector<pair<int, int>> v; for(int i=0; i<n; i++){ if(l[i] > r[i]) swap(l[i], r[i]); v.push_back({l[i], r[i]}); } sort(v.begin(), v.end()); vector<pair<int, int>> c; int max_r = 0; for(auto [l, r] : v){ if(max_r < r){ if(max_r >= l){ if(!c.empty()){ inter[c.size()] = (max_r - l + 1) * (max_r - l + 1); } } c.push_back({l, r}); max_r = r; } } n = c.size(); dp[0][0] = 0; for(int i=1; i<=n; i++) dp[i][0] = 1e9; for(int i=1; i<=n; i++){ for(int k=1; k<=K; k++){ dp[i][k] = 1e9; for(int j=0; j<i; j++){ ll cost = (c[i - 1].second - c[j].first + 1) * (c[i - 1].second - c[j].first + 1); dp[i][k] = min(dp[i][k], dp[j][k - 1] + cost - inter[j]); } } } return dp[n][K]; }

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...