제출 #291233

#제출 시각아이디문제언어결과실행 시간메모리
291233peti1234Aliens (IOI16_aliens)C++17
25 / 100
253 ms4736 KiB
#include <bits/stdc++.h> using namespace std; const int c=502; long long dp[c][c]; vector<pair<int, int> > sz; long long take_photos(int n, int m, int t, vector<int> x, vector<int> y) { for (int i=0; i<n; i++) { int a=min(x[i], y[i]), b=max(x[i], y[i]); sz.push_back({a, b}); } sort(sz.begin(), sz.end()); for (int i=1; i<=n; i++) for (int j=0; j<=t; j++) dp[i][j]=1e9; for (int i=0; i<n; i++) for (int j=0; j<t; j++) { int maxi=-1, e=sz[i].first, h=0; for (int k=0; k<i; k++) maxi=max(maxi, sz[k].second); maxi=max(0, maxi-e+1); for (int k=i; k<n; k++) { h=max(h, sz[k].second); if (h>=maxi+e) dp[k+1][j+1]=min(dp[k+1][j+1], dp[i][j]+(h-e+1)*(h-e+1)-maxi*maxi); //cout << "dp " << i << " " << k+1 << " " << j+1 << " " << dp[k+1][j+1] << "\n"; } } return dp[n][t]; }
#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...