제출 #138445

#제출 시각아이디문제언어결과실행 시간메모리
138445HassoonyAliens (IOI16_aliens)C++17
4 / 100
2 ms504 KiB
#include <bits/stdc++.h> #include "aliens.h" //#include "grader.cpp" using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MX=1009; const ll inf = (1ll<<60); ll dp[MX][MX]; int n,k; vector<pii>v1; bool cmp(pii a,pii b){ if(a.second == b.second) return a.first > b.first; return a.second < b.second; } vector<pair<ll,ll> >a; ll take_photos(int N, int m, int K, vector<int> r, vector<int> c) { n=N;k=K; for(int i=0;i<n;i++){ if(r[i] > c[i])swap(c[i],r[i]); v1.push_back({c[i],r[i]}); } sort(v1.begin(),v1.end(),cmp); a.push_back({-5,-5}); a.push_back(v1[0]); for(int i=1;i<n;i++){ if(v1[i].first <= a.back().first) continue; a.push_back(v1[i]); } n=a.size() - 1; sort(a.begin(),a.end()); // for(auto pp:a)cout<<pp.first<<" "<<pp.second<<endl; for(int u=1;u<=k;u++){ for(int i=1;i<=n;i++)dp[u][i]=inf; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ ll Cost = (a[i].first - a[j].second + 1) * (a[i].first - a[j].second + 1); ll Inter = (max(0ll,a[j-1].first - a[j].second + 1)) * (max(0ll,a[j-1].first - a[j].second + 1)); dp[u][i] = min(dp[u][i], dp[u-1][j-1] + Cost - Inter); } } } return dp[k][n]; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 */
#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...