Cod sursa(job #1525784)

Utilizator backtrackIconaru Marian Catalin backtrack Data 15 noiembrie 2015 16:20:22
Problema Transport Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 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/k+1;
	int lower_bound=upper_bound;
	upper_bound*=n/k+1;
	
	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;
	}