제출 #400214

#제출 시각아이디문제언어결과실행 시간메모리
400214rocks03Aliens (IOI16_aliens)C++14
12 / 100
278 ms348 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define ff first #define ss second #define pb push_back #define SZ(x) ((int)(x).size()) #define all(x) x.begin(), x.end() #define debug(x) cout << #x << ": " << x << " " #define nl cout << "\n" #define rep(i, a, b) for(int i = (a); i < (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); long long take_photos(int N, int M, int K, vector<int> X, vector<int> Y){ vector<int> v[M + 1]; rep(i, 0, N){ v[X[i]].pb(Y[i]); v[Y[i]].pb(X[i]); } vector<ll> dp(M + 1, LLONG_MAX), dp2(M + 1, LLONG_MAX); dp[0] = dp2[0] = 0; rep(i, 1, M + 1){ if(SZ(v[i - 1])) break; dp[i] = 0; } rep(k, 1, K + 1){ rep(i, 1, M + 1){ if(!SZ(v[i - 1])){ dp2[i] = dp2[i - 1]; continue; } int l = 1; per(j, i - 1, 0){ for(int x : v[j]) l = max(l, i - x); if(i - j >= l && dp[j] != LLONG_MAX){ ll cost = l; cost = cost * cost; dp2[i] = min(dp2[i], dp[j] + cost); } } } swap(dp, dp2); } return dp[M]; }
#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...