ikbal's blog

By ikbal, 11 years ago, In English

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 read(){
	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);
	
	int N = read() ; 
	A = read() , B = read() , C = read();
	
	For(i,1,N){
		ar[i].fi = read();
		ar[i].se = read();
	}
	
	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;

  • Vote: I like it
  • -5
  • Vote: I do not like it