Submission #490253

#TimeUsernameProblemLanguageResultExecution timeMemory
490253cpp219Holding (COCI20_holding)C++14
110 / 110
80 ms6744 KiB
#include<bits/stdc++.h> #define ll int #define ld long double #define fs first #define sc second #define debug(y) cout<<y,exit(0) using namespace std; typedef pair<ll,ll> LL; const ll N = 1e2 + 9; const ll mod = 1e9 + 7; const ll base = 31; ll n,l,r,k,dp[N][N*N],prv[N][N*N],a[N]; int main(){ ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); #define task "tst" if (fopen(task".inp","r")){ freopen(task".inp","r",stdin); //freopen(task".out","w",stdout); } cin>>n>>l>>r>>k; for (ll i = 1;i <= n;i++) cin>>a[i]; for (ll pos = r;pos >= l;pos--){ for (ll cur = r;cur <= n;cur++){ for (ll rm = 0;rm <= k;rm++){ ll &res = dp[cur][rm]; if (cur == r) res = prv[cur][rm] + a[pos]; else{ ll d = abs(cur - pos); res = min(dp[cur - 1][rm],prv[cur][rm] + a[pos]); if (rm >= d) res = min(res,prv[cur - 1][rm - d] + a[cur]); } } } for (ll cur = l;cur > 0;cur--){ for (ll rm = 0;rm <= k;rm++){ ll &res = dp[cur][rm]; if (cur == l) res = dp[n][rm]; else{ ll d = abs(cur - pos); res = min(dp[cur + 1][rm],prv[cur][rm] + a[pos]); if (rm >= d) res = min(res,prv[cur + 1][rm - d] + a[cur]); } } } for (ll i = 1;i <= n;i++) for (ll j = 0;j <= k;j++) prv[i][j] = dp[i][j]; } cout<<dp[1][k]; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

Compilation message (stderr)

holding.cpp: In function 'int main()':
holding.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...