#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"
int n,i,x,y,ans,xans[2005],yans[2005];
int b[2005],p[2005],u[2005],dp[2005][205][405],dpmin[2005][405];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("input.000","r",stdin);
// freopen("output.000","w",stdout);
// srand((unsigned)time(NULL));
// rand()
cin>>n;
for (i=1;i<n+1;i++) cin>>b[i];
for (i=1;i<n;i++) cin>>p[i];
for (i=1;i<n;i++) cin>>u[i];
for (i=1;i<n+1;i++) for (x=0;x<=200;x++) for (y=0;y<=400;y++) dp[i][x][y]=1e18;
for (i=1;i<n+1;i++) for (y=0;y<=400;y++) dpmin[i][y]=1e18;
for (x=0;x<=u[1];x++) for (y=0;y<=b[2];y++)
if (x+y<=p[1] and p[1]-x-y<=b[1]) dp[1][x][y]=x;
for (y=0;y<=b[2];y++)
{
if (y>0) dpmin[1][y]=dpmin[1][y-1];
for (x=0;x<=u[1];x++) dpmin[1][y]=min(dpmin[1][y], dp[1][x][y]);
}
for (i=2;i<n;i++)
{
for (x=0;x<=u[i];x++) for (y=0;y<=b[i+1];y++)
if (x+y<=p[i] and p[i]-x-y<=b[i]) dp[i][x][y]=x+dpmin[i-1][b[i]-(p[i]-x-y)];
for (y=0;y<=b[i+1];y++)
{
if (y>0) dpmin[i][y]=dpmin[i][y-1];
for (x=0;x<=u[i];x++) dpmin[i][y]=min(dpmin[i][y], dp[i][x][y]);
}
}
ans=1e18;
for (y=0;y<=b[n];y++) ans=min(ans, dpmin[n-1][y]);
if (ans>3e15) cout<<"NO";else
{
cout<<"YES\n"<<ans<<"\n";
for (x=0;x<=u[n-1];x++) for (y=0;y<=b[n];y++)
if (x+y<=p[n-1] and p[n-1]-x-y<=b[n-1])
if (dp[n-1][x][y]==ans)
{
xans[n-1]=x;
yans[n-1]=y;
}
p[0]=b[0]=1e18;
for (i=n-2;i>0;i--)
for (x=0;x<=u[i];x++)
if (x+b[i+1]-(p[i+1]-xans[i+1]-yans[i+1])<=p[i-1] and p[i]-x-b[i+1]+(p[i+1]-xans[i+1]-yans[i+1])<=b[i-1])
if (xans[i+1]+dp[i][x][b[i+1]-(p[i+1]-xans[i+1]-yans[i+1])]==dp[i+1][xans[i+1]][yans[i+1]])
{
xans[i]=x;
yans[i]=b[i+1]-(p[i+1]-xans[i+1]-yans[i+1]);
}
for (i=1;i<n;i++) cout<<p[i]-xans[i]-yans[i]<<" "<<xans[i]<<" "<<yans[i]<<"\n";
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:25:76: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
25 | for (i=1;i<n+1;i++) for (x=0;x<=200;x++) for (y=0;y<=400;y++) dp[i][x][y]=1e18;
| ^~~~
Main.cpp:26:55: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
26 | for (i=1;i<n+1;i++) for (y=0;y<=400;y++) dpmin[i][y]=1e18;
| ^~~~
Main.cpp:49:6: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
49 | ans=1e18;
| ^~~~
Main.cpp:64:13: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
64 | p[0]=b[0]=1e18;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
