### ikbal's blog

By ikbal, 10 years ago,

problem statement is here .

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <ctime>
#include <queue>
#include <map>
#include <list>
#include <fstream>
#include <iomanip>
#include <set>

#define For(i,a,b) for(int (i)=(a);(i)<=int(b);(i)++)
#define Ford(i,a,b) for(int (i)=(a);(i)>=int(b);(i)--)
#define Rep(i,a,b) for(int (i)=(a);(i)<int(b);(i)++)
#define foreach(it,x) for(__typeof(x.begin()) it = x.begin() ; it!=x.end() ; it++ )
#define fi first
#define se second
#define dbg(x) cerr<<#x<<":"<<(x)<<endl
#define dg(x) cerr<<#x<<":"<<(x)<<' '
#define fill(x,y) memset(x,y,sizeof x)
#define all(x) x.begin(),x.end()
#define bin(x) (1LL<<(x))
#define gcd __gcd
#define pb push_back

using namespace std;

typedef long long Lint;
typedef pair<int,int> ii;
typedef pair<Lint,Lint> Lii;
typedef pair<int,ii> iii;

const int inf = 1e9+5;
const Lint Linf = 1e18+5;

template<class T> inline void umax(T &a,T b){if(a<b) a = b ; }
template<class T> inline void umin(T &a,T b){if(a>b) a = b ; }
template<class T> inline T abs(T a){return a>0 ? a : -a;}
template<class T> inline T lcm(T a,T b){
return a/gcd(a,b)*b;
}

int res = 0 ;
int neg ;
while(true){
char ch = getchar();
if((ch>='0' && ch<='9') || ch=='-'){
if(ch=='-') neg = -1;
else neg = 1 , res = ch-'0';
break;
}
}
while(true){
char ch = getchar();
if(ch>='0' && ch<='9') res*=10 , res+=ch-'0';
else break;
}
return res*neg;
}
void print(int x){
if(x==0){
putchar('0');
putchar('\n');
return ;
}
static char buf[20];
int nn = 0 ;
if(x<0) putchar('-') , x*=-1;
while(x){
buf[++nn] = x%10+'0';
x/=10;
}
Ford(i,nn,1) putchar(buf[i]);
putchar('\n');

}

const int MAXN = 1010;

ii ar[MAXN];
vector<ii> v[MAXN];
int A, B ,C;

class fenwick{
public:
int *T;
int n;
vector<int> vals;
map<int,int> name;
void init(vector<ii> v){
Rep(i,0,n)
T[i] = 0;
vals.clear();
name.clear();
foreach(it,v){
vals.pb(A*it->fi+B*it->se);
}
sort(all(vals));
int p = 1 ;
Rep(i,0,vals.size()){
if(i>0 && vals[i]!=vals[i-1]) p++;
name[vals[i]] = p ;
}
}
fenwick(int _n=0){
n = _n+5;
T = new int[n];
}
void update(int x,int val){
x = name[x];
for(int i=x;i<n;i+=i&-i)
T[i]+=val;
}
int get(int r){
int idx = upper_bound(all(vals),r)-vals.begin();
if(idx<0) return 0;
if(upper_bound(all(vals),r)==vals.end()) idx--;
r = name[vals[idx]];
int res = 0 ;
for(int i=r;i>0;i-=i&-i)
res+=T[i];
return res;
}
};

bool cmp(const ii &a,const ii &b){
return a.se < b.se ;
}

int main(){

freopen("tryout.in","r",stdin);
freopen("tryout.out","w",stdout);

For(i,1,N){
}

sort(ar+1,ar+1+N);

For(i,1,N){
For(j,i,N)
v[i].pb(ar[j]);
sort(all(v[i]),cmp);
}

fenwick F(N);

int ans = 0 ;

For(i,1,N){
int hmin = ar[i].fi;
F.init(v[i]);
Ford(j,(int)v[i].size()-1,0){
int wmin = v[i][j].se;
int cc = C + hmin * A + wmin * B ;
F.update(A*v[i][j].fi+B*v[i][j].se,1);
umax(ans,F.get(cc));
}
}

print(ans);

return 0;
}



WHY this code gets WA.?

UPD: i finded the bug. in get function idx must be like that int idx = upper_bound(all(vals),r)-vals.begin()-1;

• -5