Cod sursa(job #1525809)

Utilizator backtrackIconaru Marian Catalin backtrack Data 15 noiembrie 2015 16:44:40
Problema Transport Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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;
	int solution=0;
	int lower_bound=0;
	for(int i=0;i<n;i++){
		f>>v[i];
		lower_bound=max(lower_bound,v[i]);
		solution+=v[i];
	}	
	upper_bound=solution;
	do{
		int i;
		int sum=(lower_bound+upper_bound)/2;
	    int nrtr=k;
		for(i=0;i<n;i++){
			sum-=v[i];
			if(sum==0){
				nrtr--;
				sum=(lower_bound+upper_bound)/2;
			}
			else if(sum<0){
				nrtr--;
				sum=(lower_bound+upper_bound)/2-v[i];
			}

		
		}
		if((nrtr>=1 && sum>=0) || (nrtr==0 && sum==(upper_bound+lower_bound)/2)){
			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<=0);
	ofstream g("transport.out");
	g<<solution;
	f.close();
	g.close();
	//system("pause");
	return 0;
	}