I was working on the USACO problem arithmetic progression.
You can see the problem (and a solution) here - http://massivealgorithms.blogspot.com/2015/08/arithmeticprogressions-codetrick.html
My code successfully runs for the first 7 test cases. However, once it reaches test case 8 (22,250) it times out. What modifications should I make to make my code more efficent? Most solutions I found online were also o(m^2*n) complexity, so I'm not sure what I need to change.
Here is my code:
//#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ofstream fout("ariprog.out");
ifstream fin("ariprog.in");
int n, m;
fin >> n >> m;
int bisquare[125001] = {};
for (int a = 0; a <= m; a++) {
for (int b = a; b <= m; b++) {
bisquare[(a*a) + (b*b)] = 1;
}
}
int max = 2 * m*m;
int value;
bool tb = false;
pair<int, int> all[125001];
int yeah = 0;
for (int s = 0; s <= max/2; s++) {
for (int i = 1;i<=max/2; i++) {
for (int x = 0; x < n; x++) {
value = s + x*i;
if (value > max) {
tb = true;
break;
}
if (!bisquare[value]) break;
if (bisquare[value] && x==n-1) {
all[yeah] = make_pair(i,s);
yeah++;
}
}
if (tb) {
tb = false;
break;
}
}
}
sort(all,all+yeah);
for (int i = 0; i < yeah; i++) {
fout << all[i].second << " " << all[i].first << endl;
}
if (all[0].first == 0) {
fout << "NONE" << endl;
}
}