제출 #1079401

#제출 시각아이디문제언어결과실행 시간메모리
1079401ALeonidouAliens (IOI16_aliens)C++17
12 / 100
71 ms2444 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define ll int #define F first #define S second #define sz(x) (ll)x.size() #define pb push_back #define INF 1000000000000000000 typedef vector <ll> vi; typedef pair <ll,ll> ii; typedef vector <ii> vii; #define dbg(x) cout<<#x<<": "<<x<<endl; #define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl; #define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl; void printVct(vi &v){ for (ll i= 0; i<sz(v); i++){ cout<<v[i]<<" "; } cout<<endl; } #define N 501 long long dp[N+1][N+1]; vector <long long> v; ll n; long long solve(ll u, ll k){ if (u >= n) return 0; if (k <= 0) return INF; if (dp[u][k] != -1) return dp[u][k]; long long ans = INF; for (ll i =u+1; i<=n; i++){ long long d = (v[i-1] - v[u] + 1LL); ans = min(ans, solve(i, k-1) + d * d); } return dp[u][k] = ans; } long long take_photos(int nn, int m, int k, vector<int> r, vector<int> c) { for (ll i =0; i<=N; i++){ for (ll j = 0; j<=N; j++){ dp[i][j] = -1; } } sort(r.begin(), r.end()); v.pb(r[0]); for (ll i =1; i<nn; i++){ if (v.back() != r[i]){ v.pb(r[i]); } } n = sz(v); long long ans = solve(0, min(k,n)); return ans; } /* 4 7 3 1 1 2 2 4 4 6 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...