OJ Board

Yes, actually my first solution was O(N^4) with small constant.
Thanks, krijger, I've understood your algorithm.

I had to use bit masks to get the O(N^3) complexity. I won't call my algorithm as Floyd's modification, although I used Floyd to find shortest distances between every pair of vertices. Is there any O(N^3) algorithm without bit masks?

Maybe the greedy solution is the following: take vertices one by one, and put each of them in the class where it creates less number of pairs with already added vertices.

Then it's probably some error in your code. I've accepted this task with both STL and mine priority queues.

Do you use heap?

I used prime sieve and implemented Suspect function as it is described in problem statement. All values are stored as unsigned int (not int64). No special optimization. Time: 0:02.682.

Are the tests for this problem correct?

If all number in the sequence are nonegative, then task can be easily solved with linear algorithm like ilovenwd's one.
In case of negative values there's following O(n*log(n)) algorithm:


#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

struct prefix
{
int sum,pos ...

Thank you for test cases. They helped me to understand that my algorithm is wrong.

Could anybody tell me what's wrong in my solution?


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <vector>
#include <string>

using namespace std;

#define For(i,a,b) for(int i=(a); i<=(b); i++)
#define Rep(i,n) for(int i=0; i<(n); i ...