Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll long long
- #define N ((int)6e4 + 5)
- #define MOD ((int)1e9 + 7)
- #define MAX ((int)1e9 + 7)
- #define MAXL ((ll)1e18 + 7)
- #define MAXP ((int)1e3 + 7)
- #define thr 1e-8
- #define pi acos(-1) /// pi = acos ( -1 )
- #define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
- #define endl "\n"
- using namespace std;
- int arr[5005];
- /// we take 'cnt' times from tank 'from' to tank 'too'
- void Print(int from , int too, int cnt , int k)
- {
- int water = min(cnt*k , arr[from]); /// total amount of water taken
- if(cnt*k - k >= arr[from]) assert(0);
- arr[too] += water;
- arr[from] -= water;
- cout<<cnt<<" "<<from<<" "<<too<<endl;
- }
- /// pouring all water from all tanks in vector 'tanks' to a single tank
- void GatherAtOne(vector < int >& tanks, int k){
- for(int cur:tanks){
- if(cur != tanks.back() && arr[cur] > 0){
- Print(cur , tanks.back(), (arr[cur] + k - 1)/k, k);
- }
- }
- }
- int dpp[5005][5005] , Rem[5005];
- bool Solve(int cur , int rem , int mod)
- {
- if(rem < 0) rem += mod;
- if(cur == 0){
- return rem == 0;
- }
- if(dpp[cur][rem] != -1) return dpp[cur][rem];
- return dpp[cur][rem] = Solve(cur - 1 , rem , mod) | Solve(cur - 1 , rem - Rem[cur], mod);
- }
- /// 'taken' will contain the indexes of tanks taken, 'notTaken' will contain the
- /// indexes of the tanks not taken
- void PathPrint(int cur , int rem , int mod , vector < int >& taken , vector < int >& notTaken)
- {
- if(rem < 0) rem += mod;
- if(cur == 0) return;
- if(Solve(cur - 1 , rem , mod)){
- notTaken.push_back(cur);
- PathPrint(cur-1 , rem , mod , taken , notTaken);
- }
- else{
- taken.push_back(cur);
- PathPrint(cur - 1 , rem - Rem[cur] , mod , taken , notTaken);
- }
- }
- int main()
- {
- //assert(0);
- fastio;
- int n , k , v;
- cin>>n>>k>>v;
- int sum = 0;
- for(int i = 1 ; i <= n ; i++){
- cin>>arr[i];
- sum += arr[i];
- Rem[i] = arr[i] % k;
- }
- if(sum < v){
- cout<<"NO\n";
- return 0;
- }
- Rem[0] = v % k;
- memset(dpp,-1,sizeof dpp);
- if(Solve(n , Rem[0] , k) == 0){
- cout<<"NO\n";
- return 0;
- }
- cout<<"YES\n";
- vector < int > taken , notTaken;
- PathPrint(n , Rem[0] , k , taken, notTaken);
- GatherAtOne(taken , k);
- GatherAtOne(notTaken , k);
- int sink , source ;
- if(taken.size() > 0) sink = taken.back();
- else if(notTaken.back() == 1) sink = 2;
- else sink = 1;
- if(notTaken.size() > 0) source = notTaken.back();
- else if(taken.back() == 1) source = 2;
- else source = 1;
- if(arr[sink] < v){
- Print(source , sink , (v-arr[sink])/k , k);
- }
- else if(arr[sink] > v){
- Print(sink , source , (arr[sink] - v)/k , k);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement