Submission #523858

#TimeUsernameProblemLanguageResultExecution timeMemory
523858Killer2501Holding (COCI20_holding)C++14
0 / 110
0 ms332 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 1e2+2; const int M = N*N/4+2; const int inf = 1e9+7; const ll mod = 998244353; int n, t, m, k, ans, tong, a[N], dpr[N][N][M], dpl[N][N][M], l, r; vector<pll> adj[N]; vector<ll> vi; string s; void sol() { cin >> n >> l >> r >> k; for(int i =1 ; i <= n; i ++) { cin >> a[i]; tong += a[i]; } k = min(k, n*n/4+2); for(int i = l; i <= r; i ++) { for(int j = l-1; j > 0; j --) { for(int p = 0; p <= k; p ++) { dpl[i][j][p] = inf; if(i > l)dpl[i][j][p] = min(dpl[i-1][j][p]+a[i], dpl[i][j][p]); if(j < l-1)dpl[i][j][p] = min(dpl[i][j][p], dpl[i][j+1][p]+a[i]); if(p)dpl[i][j][p] = min(dpl[i][j][p], dpl[i][j][p-1]); if(i-j <= p)dpl[i][j][p] = min(dpl[i][j][p], dpl[i-1][j+1][p-i+j]+a[j]); //cout << i <<" "<<j<<" "<<p<<" "<<dpl[i][j][p]<<'\n'; } } } for(int i = r; i >= l; i --) { for(int j = r+1; j <= n; j ++) { for(int p = 0; p <= k; p ++) { dpr[i][j][p] = inf; if(i < r)dpr[i][j][p] = min(dpr[i+1][j][p]+a[i], dpr[i][j][p]); if(j > r+1)dpr[i][j][p] = min(dpr[i][j][p], dpr[i][j-1][p]+a[i]); if(p)dpr[i][j][p] = min(dpr[i][j][p], dpr[i][j][p-1]); if(j-i <= p)dpr[i][j][p] = min(dpr[i][j][p], dpr[i+1][j-1][p+i-j]+a[j]); } } } if(l > 1)ans = dpl[r][1][k]; else if(r < n)ans = dpr[l][n][k]; else ans = tong; if(l > 1 && r < n) { for(int i = l; i <= r; i ++) { for(int p = 0; p <= k; p ++) ans = min(ans, dpl[i][1][p]+dpr[i+1][n][k-p]); } } cout << ans; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int ntest = 1; //cin >> ntest; while(ntest -- > 0) sol(); }

Compilation message (stderr)

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