Advertisement
_no0B

Untitled

Nov 21st, 2021
751
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.81 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define N ((int)6e4 + 5)
  4. #define MOD ((int)1e9 + 7)
  5. #define MAX ((int)1e9 + 7)
  6. #define MAXL ((ll)1e18 + 7)
  7. #define MAXP ((int)1e3 + 7)
  8. #define thr 1e-8
  9. #define pi acos(-1)  /// pi = acos ( -1 )
  10. #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
  11. #define endl "\n"
  12.  
  13. using namespace std;
  14.  
  15. int arr[5005];
  16. /// we take 'cnt' times from tank 'from' to tank 'too'
  17. void Print(int from , int too, int cnt , int k)
  18. {
  19.     int water = min(cnt*k , arr[from]); /// total amount of water taken
  20.     if(cnt*k - k >= arr[from]) assert(0);
  21.     arr[too] += water;
  22.     arr[from] -= water;
  23.     cout<<cnt<<" "<<from<<" "<<too<<endl;
  24. }
  25.  
  26. /// pouring all water from all tanks in vector 'tanks' to a single tank
  27. void GatherAtOne(vector < int >& tanks, int k){
  28.     for(int cur:tanks){
  29.         if(cur != tanks.back() && arr[cur] > 0){
  30.             Print(cur , tanks.back(), (arr[cur] + k - 1)/k, k);
  31.         }
  32.     }
  33. }
  34.  
  35. int dpp[5005][5005] , Rem[5005];
  36.  
  37. bool Solve(int cur , int rem , int mod)
  38. {
  39.     if(rem < 0) rem += mod;
  40.     if(cur == 0){
  41.         return rem == 0;
  42.     }
  43.     if(dpp[cur][rem] != -1) return dpp[cur][rem];
  44.     return dpp[cur][rem] = Solve(cur - 1 , rem , mod) | Solve(cur - 1 , rem - Rem[cur], mod);
  45. }
  46.  
  47. /// 'taken' will contain the indexes of tanks taken, 'notTaken' will contain the
  48. /// indexes of the tanks not taken
  49. void PathPrint(int cur , int rem , int mod , vector < int >& taken , vector < int >& notTaken)
  50. {
  51.     if(rem < 0) rem += mod;
  52.     if(cur == 0) return;
  53.     if(Solve(cur - 1 , rem , mod)){
  54.         notTaken.push_back(cur);
  55.         PathPrint(cur-1 , rem , mod , taken , notTaken);
  56.     }
  57.     else{
  58.         taken.push_back(cur);
  59.         PathPrint(cur - 1 , rem - Rem[cur] , mod , taken , notTaken);
  60.     }
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66.     //assert(0);
  67.     fastio;
  68.     int n , k , v;
  69.     cin>>n>>k>>v;
  70.     int sum = 0;
  71.     for(int i = 1 ; i <= n ; i++){
  72.         cin>>arr[i];
  73.         sum += arr[i];
  74.         Rem[i] = arr[i] % k;
  75.     }
  76.     if(sum < v){
  77.         cout<<"NO\n";
  78.         return 0;
  79.     }
  80.     Rem[0] = v % k;
  81.     memset(dpp,-1,sizeof dpp);
  82.     if(Solve(n , Rem[0] , k) == 0){
  83.         cout<<"NO\n";
  84.         return 0;
  85.     }
  86.     cout<<"YES\n";
  87.     vector < int > taken , notTaken;
  88.     PathPrint(n , Rem[0] , k , taken, notTaken);
  89.  
  90.     GatherAtOne(taken , k);
  91.     GatherAtOne(notTaken , k);
  92.  
  93.     int sink , source ;
  94.     if(taken.size() > 0) sink = taken.back();
  95.     else if(notTaken.back() == 1) sink = 2;
  96.     else sink = 1;
  97.  
  98.     if(notTaken.size() > 0) source = notTaken.back();
  99.     else if(taken.back() == 1) source = 2;
  100.     else source = 1;
  101.  
  102.     if(arr[sink] < v){
  103.         Print(source , sink , (v-arr[sink])/k , k);
  104.     }
  105.     else if(arr[sink] > v){
  106.         Print(sink , source , (arr[sink] - v)/k , k);
  107.     }
  108.     return 0;
  109. }
  110.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement