fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define REP(i,n) for(int i = 0;i<n;i++)
  3. #define REPD(i,n) for(int i = n-1;i>=0;i--)
  4. #define FOR(i,a,b) for(int i = a;i<=b;i++)
  5. #define WL(n) while(n--)
  6. #define all(v) v.begin(),v.end()
  7. #define int long long
  8. #define double long double
  9. #define pii pair<int,int>
  10. #define vi vector<int>
  11. #define vvi vector<vector<int>
  12. #define mii map<int,int>
  13. #define mp make_pair
  14. #define pb push_back
  15. #define F first
  16. #define S second
  17. #define print(x) cout << x << "\n";
  18. #define debug(x) cout << x << "\n";
  19. #define debug2(x,y) cout << x << " " << y << "\n";
  20. #define debug3(x,y,z) cout << x << " " << y << " " << z << "\n";
  21. #define debug4(x,y,z,xx) cout << x << " " << y << " " << z << " " << xx << "\n";
  22. #define debug5(x,y,z,xx,yy) cout << x << " " << y << " " << z << " " << xx << " " << yy << "\n";
  23. const int INF = (int)(1e14-1);
  24. const int MOD = (int)(1e9+7);
  25.  
  26. using namespace std;
  27.  
  28. void solve();
  29.  
  30. signed main()
  31. {
  32.     int t;
  33.     cin >> t;
  34.     WL(t) solve();
  35. }
  36.  
  37. const int LIM = 5005;
  38. int n,m;
  39. int q[LIM];// duration
  40. pii p[LIM];//F = alien time, S = duration
  41.  
  42. void solve()
  43. {
  44.       cin >> n >> m;
  45.       REP(i,n) cin >> q[i];
  46.       REP(i,n) q[i];
  47.       REP(i,m) cin >> p[i].S;
  48.       REP(i,m) p[i].S;
  49.       REP(i,m) cin >> p[i].F;
  50.       reverse(q,q+n);
  51.       sort(p,p+m,greater<pii>());
  52.       int dp[n+1][m+1];
  53.       REPD(pi,m+1) REPD(ci,n+1)
  54.       {
  55.         	if(pi==m&&ci==n)
  56.         	{
  57.       	  	dp[ci][pi] = 0;
  58.       	  	continue;
  59.       	  }
  60.       	  int t1 = INF,t2 = INF;
  61. 		    if(ci<n) t1 = dp[ci+1][pi]+q[ci];
  62. 		    if(pi<m)
  63. 		    {
  64. 		        int before = dp[ci][pi+1];
  65. 		        int after = before+p[pi].S;
  66. 		        int alien = p[pi].F;
  67. 		        if(before<alien&&alien<=after)
  68. 		        {
  69. 		            t2 = after;
  70. 		        }
  71. 		        else if(alien>after)
  72. 		        {
  73. 		             int delay = alien-after;
  74. 		            after+=delay;
  75. 		            t2 = after;
  76. 		        }
  77. 		    }
  78. 		    int ans = min(t1,t2);
  79. 		    dp[ci][pi] = ans;
  80. 		    //debug3(ci,pi,ans);
  81.       }
  82.       int ans = dp[0][0];
  83.       if(ans==INF) ans = -1;
  84.       print(ans);
  85. }
Success #stdin #stdout 0s 15352KB
comments (?)
stdin
copy 
2
4 2
3 4 1 2
3 2
4 9
4 2
3 4 1 1
3 2
4 9
stdout
copy 
16
15
https://ideone.com/CQulix
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!