Pizza Locations

This message was edited 3 times. Last update was at 19/06/2011 07:11:03

Добивам TLE. http://www.spoj.pl/problems/PIZZALOC/
Некој совет за оптимизација?

// http://www.spoj.pl/problems/PIZZALOC/

#include <cstdlib>
#include <fstream>
#include <vector>
#include <string>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct locat
{
	int x, y;
	bool b[100];
};
struct solit
{
	int x, y, s;
};

int main()
{
	int k, r, m, n, cnt, mx=0; 
	locat loc[20];
	solit sol[100];
	vector<int> v;
	bool vis[100];

cin >> k >> r;
	cin >> m;

for (int i=0; i<m; i++)
		cin >> loc[i].x >> loc[i].y;

cin >> n;

for (int i=0; i<n; i++)
	{
		cin >> sol[i].x >> sol[i].y >> sol[i].s;
		for (int j=0; j<m; j++)
		{
			if ((sol[i].x-loc[j].x)*(sol[i].x-loc[j].x) + (sol[i].y-loc[j].y)*(sol[i].y-loc[j].y) <= r*r) //dali e vo radius
				loc[j].b[i]=true;
			else
				loc[j].b[i]=false;
		}
	}

for (int i=1; i<(1<<m); i++)
	{
		cnt=0;
		v.clear();
		for (int l=0; l<n; l++)
			vis[l]=false;

for (int j=0; j<m; j++) //generiram podmnozestva
			if (i&1<<j) 
				v.push_back(j);

if (v.size()==k)
		{
			for (int d=0; d<v.size(); d++) //ako e vo radius na lokacijata go dodavam
			for (int l=0; l<n; l++)
				if (loc[v[d]].b[l] && !vis[l]) 
				{
					cnt+=sol[l].s;
					vis[l]=true;
				}
		}

if (cnt>mx)
			mx=cnt;
	}
		
	cout << mx << endl;
	return 0;
}

Мислам дека сите програмери најмногу мразат кога ќе напишат некој код за некоја задача, и дури кога ќе завршат сфаќаат дека задачата не требало да се решава така, и треба да почнат сосема од почеток. Затоа те советувам секогаш да ја предвидиш сложеноста на твојот алгоритам. Ова ти што си го искуцал е чист brutefoce. На натпревариве алгоритамските задачи скоро никогаш не ги прават да бидат толку очигледни. Затоа првиот код што треба да го планираш да го куцаш, секогаш нека ти биде некоја добра оптимизација на bruteforce, или алгоритам што сигурно ќе биде точен и побрз од brutefoce. Нема потреба да вежбаш програмирање со куцање brutefoce на задачите.

Е сега, во врска со задачата, единственото решение што мене ми текнува е max flow со bfs - ford fulkerson, имплементација и објаснување можеш да најдеш на Topcoder. Мислам дека не постои друг начин да се реши ова.
Треба да куцаш нов код. Не може да очекуваш дека некоја оптимизација со додавање на два IF-a , ќе биде доволно задачава да пројде.