Submission #1079392

#TimeUsernameProblemLanguageResultExecution timeMemory
1079392ALeonidouAliens (IOI16_aliens)C++17
0 / 100
1 ms1372 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 500 ll dp[N+1][N+1]; vi v; ll n; long long solve(ll u, ll k){ // dbg2(u,k); if (u >= n) return 0; if (k <= 0) return INF; if (dp[u][k] != -1) return dp[u][k]; long long ans = solve(u+1, k-1) + 1; for (ll i =u+2; i<=n; i++){ ll d = (v[i-1] - v[u] + 1); 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) { n =nn; for (ll i =0; i<=N; i++){ for (ll j = 0; j<=N; j++){ dp[i][j] = -1; } } for (ll i =0; i<n; i++){ v.pb(r[i]); } long long ans = solve(0, min(k,n)); return ans; } /* 4 7 2 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...