제출 #828526

#제출 시각아이디문제언어결과실행 시간메모리
828526devariaotaNetwork (BOI15_net)C++17
0 / 100
2 ms340 KiB
#include <bits/stdc++.h> #define inf INT_MAX #define longlonginf LONG_LONG_MAX #define mod 998244353 #define MAXN 5000 #define pll pair<ll,ll> #define ll long long #define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]"; #define yes() cout<<"YES\n"; #define no() cout<<"NO\n"; using namespace std; ll n,m,k,q,x; ll h; ll ans = 0; string subtask; ll sub3 = 0; void solve(){ cin>>n>>k; ll dp[2][MAXN+5]; k = min(k,(ll)5000); ll a[n]; for(int i = 0 ; i < n ; i++){ cin>>a[i]; } if( k == 0 ){ sort(a,a+n); x = 0; ans = longlonginf; for(int i = 0 ; i < n ; i++){ x += a[i]; } ll pref = 0; for(int i = 0 ; i < n ; i++){ pref += a[i]; x -= a[i]; ans = min((i+1)*a[i] - pref + x - (n-(i+1))*a[i],ans); } cout<<ans<<"\n"; return; } for(int i = 0 ; i <= MAXN ; i++){ dp[0][i] = abs(a[0]-i); } for(int i = 1 ; i < n ; i++){ multiset<ll> s; for(int j = 0 ; j < k ; j++){ s.insert(dp[0][j]); } for(int j = 0 ; j <= MAXN ; j++){ if( j + k <= MAXN ) s.insert(dp[0][j+k]); if( j - k > 0 ) s.erase(s.lower_bound(dp[0][j-k-1])); dp[1][j] = abs(a[i]-j) + *s.begin(); //cout<<i<<" "<<j<<" : "<<dp[i][j]<<"\n"; } for(int j = 0 ; j <= MAXN ; j++){ dp[0][j] = dp[1][j]; } } ans = longlonginf; for(int i = 0 ; i <= MAXN ; i++){ ans = min(ans,dp[0][i]); } cout<<ans<<"\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; //cin>>T; for(int i = 0 ; i < T ; i++){ //cout<<"Case #"<<i+1<<": "; solve(); } return 0; } /* not i but x logical operator wrong example/proof thoroughly wrong variables thinking it wrong bruh just try some test case capitals ;-; wrong data structure lol count memory usement corner case oversized array orders statements size initializer while con map -> array wrong digits?? swapped variables?? check if theres any variabled that got declared twice find some pattern name collision constraints??! mod !! resets */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...