Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<iostream>
- #include<sstream>
- #include<cstdlib>
- #include<cmath>
- #include<ctime>
- #include<iomanip>
- #include<vector>
- #include<string>
- #include<map>
- #include<queue>
- #include<set>
- #include<algorithm>
- using namespace std;
- int n,m,k;
- int y[1000];
- int x[1000];
- int rad[1000];
- int b[1000];
- bool checkLength(int i,int j,int ii,int jj,int r) {
- return ((i-ii)*(i-ii)+(j-jj)*(j-jj))<=r*r;
- }
- pair<int,int> getBounds(int i,int no) {
- int L,R; //bounds
- int v;
- if (i<=y[no])
- v=max(i,y[no]-rad[no]);
- else
- v=min(i,y[no]+rad[no]);
- if (v!=i) return make_pair(-1,-1);
- v=x[no];
- int l=0; int r=v;
- while (r-l>1) {
- int mid=(r+l)/2;
- if (checkLength(i,mid,y[no],x[no],rad[no]))
- r=mid; else l=mid;
- }
- L=r;
- l=v; r=m+1;
- while (r-l>1) {
- int mid=(r+l)/2;
- if (checkLength(i,mid,y[no],x[no],rad[no]))
- l=mid; else r=mid;
- }
- R=l;
- return make_pair(L,R);
- }
- int main() {
- freopen("inet.in","rt",stdin);
- freopen("inet.out","wt",stdout);
- scanf("%d %d %d",&m,&n,&k);
- for (int i=0;i<k;i++)
- scanf("%d %d %d %d",&y[i],&x[i],&rad[i],&b[i]);
- int ret=-1; int col=0;
- for (int i=1;i<=n;i++) {
- int sum=0;
- vector<pair<pair<int,int>,int > > left,right;
- for (int j=0;j<k;j++) {
- pair<int,int> ret = getBounds(i,j);
- if (ret.first==-1) continue;
- left.push_back(make_pair(make_pair(ret.first,ret.second),b[j]));
- right.push_back(make_pair(make_pair(ret.second,ret.first),b[j]));
- }
- sort(left.begin(),left.end());
- sort(right.begin(),right.end());
- int l1=0,r1=0;
- for (int v=1;v<=m;v++) {
- while (l1<left.size() && left[l1].first.first<=v) {
- sum+=left[l1].second;
- l1++;
- }
- if (sum>ret) {
- ret=sum;
- col=1;
- } else if (sum==ret) {
- col++;
- }
- while (r1<right.size() && right[r1].first.first<=v) {
- sum-=right[r1].second;
- r1++;
- }
- }
- }
- printf("%d\n%d",ret,col);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement