#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, A[1000005], B[1000005], C[1000005];
pii ans[1000005];
int dp[2005][4005], P[1000005];
void solve(){
cin >> n;
for(int i=1;i<=n;i++)cin >> A[i];
for(int i=1;i<n;i++)cin >> B[i];
for(int i=1;i<n;i++)cin >> C[i];
for(int i=1;i<n;i++){
/*
P[A[i] + 1] = 1e18;
for(int j=A[i];j>=0;j--){
P[j] = min(P[j+1], dp[i-1][j] + max(0ll, B[i] - A[i+1] - j));
}
for(int j=0;j<=A[i+1];j++){
if(B[i] - A[i+1] + j - C[i] > A[i])dp[i][j] = 1e18;
else dp[i][j] = P[max(0ll, B[i] - A[i+1] + j - C[i])] + j;
}
*/
for(int j=0;j<=A[i+1];j++){
dp[i][j] = 1e18;
for(int k=0;k<=A[i];k++){
int ext = B[i] - (A[i+1] - j) - k;
if(ext > C[i] || ext < 0)continue;
ext = max(ext, 0ll);
dp[i][j] = min(dp[i][j], ext + dp[i-1][k]);
}
}
}
int mn = 1e18, idx = -1;
for(int i=0;i<=A[n];i++)if(mn > dp[n-1][i])mn = dp[n-1][i], idx = i;
if(mn >= (int)1e17){
cout << "NO\n";
return;
}
int x1 = n-1, x2 = idx;
while(x1 >= 1){
//cout << x1 << ' ' << x2 << '\n';
int nd = -1, mn2= 1e18;
for(int j=0;j<=A[x1];j++){
int ext = (B[x1] - (A[x1 + 1] - x2) - j);
if(ext > C[x1] || ext < 0)continue;
ext = max(ext, 0ll);
if(dp[x1-1][j] + ext < mn2){
mn2 = dp[x1-1][j] + ext;
nd = j;
}
}
assert(mn2 == dp[x1][x2]);
ans[x1].se.se = A[x1+1] - x2;
ans[x1].se.fi = B[x1] - (A[x1+1] - x2) - nd;
ans[x1].fi = nd;
x1--;
x2 = nd;
}
cout << "YES\n";
cout << mn << '\n';
//for(int i=1;i<n;i++)cout << ans[i].fi << ' ' << ans[i].se.fi << ' ' << ans[i].se.se << '\n';
/*
for(int i=1;i<n;i++){
ans[i].fi = min(A[i], B[i]);
B[i] -= min(B[i], A[i]);
if(B[i] > A[i+1]){
cout << "NO\n";
return;
}
ans[i].se = B[i];
A[i+1] -= B[i];
}
cout << "YES\n 0\n";
for(int i=1;i<n;i++)cout << ans[i].fi << ' ' << 0 << ' ' << ans[i].se << '\n';
*/
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
Main.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
91 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
586 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Unexpected end of file - int64 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
586 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
