제출 #786260

#제출 시각아이디문제언어결과실행 시간메모리
786260Magikarp4000Aliens (IOI16_aliens)C++17
25 / 100
129 ms2308 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define OPTM ios_base::sync_with_stdio(0); cin.tie(0); #define INF int(1e9+7) #define ln '\n' #define ll long long #define ull unsigned long long #define ui unsigned int #define us unsigned short #define FOR(i,s,n) for (int i = s; i < n; i++) #define FORR(i,n,s) for (int i = n; i > s; i--) #define FORX(u, arr) for (auto u : arr) #define PB push_back #define in(v,x) (v.find(x) != v.end()) #define F first #define S second #define PII pair<int, int> #define PLL pair<ll, ll> #define UM unordered_map #define US unordered_set #define PQ priority_queue #define ALL(v) v.begin(), v.end() const ll LLINF = 1e18+1; #define int long long const int MAXN = 5e2+5; int n; int dp[MAXN][MAXN]; vector<PII> tmp,v; int sq(int x) {return x*x;} bool cmp(const PII &a, const PII &b) { if (a.F == b.F) return a.S > b.S; return a.F < b.F; } long long take_photos(int32_t N, int32_t m, int32_t k, vector<int32_t> R, vector<int32_t> C) { FOR(i,0,N) tmp.PB({min(R[i],C[i]),max(R[i],C[i])}); sort(ALL(tmp),cmp); // v.PB({-1,-1}); // padding int ma = -1LL; FOR(i,0,N) if (tmp[i].S > ma) ma = tmp[i].S, v.PB(tmp[i]); n = v.size(); // cout << ln; // FORX(u,v) cout << u.F << " " << u.S << ln; // cout << ln; FOR(j,0,k+1) dp[0][j] = 0LL; FOR(i,1,n+1) FOR(j,0,k+1) dp[i][j] = LLINF; FOR(i,1,n+1) { FOR(j,1,k+1) { FOR(l,0,i) { if (l > 0 && v[l-1].S-v[l].F+1LL > 0LL) { dp[i][j] = min(dp[i][j], dp[l][j-1]+sq(v[i-1].S-v[l].F+1LL)-sq(v[l-1].S-v[l].F+1LL)); } else { dp[i][j] = min(dp[i][j], dp[l][j-1]+sq(v[i-1].S-v[l].F+1LL)); } } } } return dp[n][k]; }
#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...