Cod sursa(job #1525676)

Utilizator backtrackIconaru Marian Catalin backtrack Data 15 noiembrie 2015 13:26:51
Problema Transport Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<iostream>
#include<fstream>
using namespace std;

int main(){
	ifstream f("transport.in");
	int n,k;
	f>>n>>k;
	int v[16000];
	int upper_bound=0;
	for(int i=0;i<n;i++){
		f>>v[i];
		upper_bound=max(upper_bound,v[i]);
	}
	int solution=upper_bound*n;
	int lower_bound=upper_bound;
	upper_bound*=n;
	
	do{
		int i;
		int sum=(lower_bound+upper_bound)/2;
	    int nrtr=k;
		for(i=0;i<n;i++){
			if(sum-v[i]>0) 
				sum-=v[i];

			else if(sum-v[i]<0){
            	sum=(lower_bound+upper_bound)/2;
				nrtr--;
				sum-=v[i];
			}
		}
		if(nrtr>=0 && sum>=0){
			solution=min(solution,(lower_bound+upper_bound)/2);
			upper_bound=(lower_bound+upper_bound)/2-1;
		}
		if(nrtr<0 || nrtr==0 && sum<0)
				lower_bound= (lower_bound+upper_bound)/2+1;
			
		
	}while(lower_bound!=upper_bound);
	ofstream g("transport.out");
	g<<solution;
	f.close();
	g.close();
	//system("pause");
	return 0;
	}