Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Why I got WA?

Posted by shouhm at 2005-07-06 16:10:32 on Problem 2465
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

const long limitn = 201;
const long L = 200;
const long M = 1;

long D, dist[limitn], price[limitn], cost, MaxDist, n;

void init()	{
	long dis, pri;
//	ifstream cin("F.in");
	cin >> D;
	n = 0;
	dist[0] = 0;	price[0] = 0;
	while (cin >> dis >> pri)	{
		n ++;
		dist[n] = dis;
		price[n] = pri;
	}
	n ++;
	dist[n] = D + L / M / 2;
	price[n] = 0;
	MaxDist = L / M;
}

void NoAnswer() {
    cout << "Impossible" << endl;
    exit(0);
}

void buy(long p, long distance)	{
	cost += distance / M * price[p];
}

void work()	{
	long i, j, p, q, remain, s;
	
	cost = 0;
	remain = L / 2;
	if (remain / M > dist[1])
		NoAnswer();
	for (i = 2; i <= n; i ++)
		if (dist[i] - dist[i - 1] > MaxDist)
			NoAnswer();
	p = 1;
	remain -= dist[p] / M;
	do
	{
		s = 0;	q = p;
		while ((s <= MaxDist) && (q < n) && (price[q] >= price[p]))	{
			q ++;
			s += (dist[q] - dist[q - 1]);
		}
		if (s <= MaxDist)	{
			if (remain >= (dist[q] - dist[p]) / M)
				remain -= (dist[q] - dist[p]) / M;
			else	{
				buy(p, dist[q] - dist[p] - remain / M);
                remain = 0;
            }
			p = q;
		}
		else	{
			buy(p, MaxDist / M - remain);
			remain = L - (dist[p + 1] - dist[p]) / M;
			p ++;
		}
	}
	while (p != n);
}

void print()	{
//	ofstream cout("F.out");
	cout << cost << endl;
}

int main()	{
	init();
	work();
	print();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator