Advertisement
Guest User

Untitled

a guest
Aug 31st, 2011
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<sstream>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<ctime>
  7. #include<iomanip>
  8. #include<vector>
  9. #include<string>
  10. #include<map>
  11. #include<queue>
  12. #include<set>
  13. #include<algorithm>
  14. using namespace std;
  15.  
  16. int n,m,k;
  17. int y[1000];
  18. int x[1000];
  19. int rad[1000];
  20. int b[1000];
  21.  
  22. bool checkLength(int i,int j,int ii,int jj,int r) {
  23.     return ((i-ii)*(i-ii)+(j-jj)*(j-jj))<=r*r;
  24. }
  25.  
  26. pair<int,int> getBounds(int i,int no) {
  27.     int L,R; //bounds
  28.     int v;
  29.     if (i<=y[no])
  30.         v=max(i,y[no]-rad[no]);
  31.     else
  32.         v=min(i,y[no]+rad[no]);
  33.     if (v!=i) return make_pair(-1,-1);
  34.     v=x[no];
  35.     int l=0; int r=v;
  36.     while (r-l>1) {
  37.         int mid=(r+l)/2;
  38.         if (checkLength(i,mid,y[no],x[no],rad[no]))
  39.             r=mid; else l=mid;
  40.     }
  41.     L=r;
  42.     l=v; r=m+1;
  43.     while (r-l>1) {
  44.         int mid=(r+l)/2;
  45.         if (checkLength(i,mid,y[no],x[no],rad[no]))
  46.             l=mid; else r=mid;
  47.     }
  48.     R=l;
  49.     return make_pair(L,R);
  50. }
  51.  
  52. int main() {
  53.     freopen("inet.in","rt",stdin);
  54.     freopen("inet.out","wt",stdout);
  55.    
  56.     scanf("%d %d %d",&m,&n,&k);
  57.     for (int i=0;i<k;i++)
  58.         scanf("%d %d %d %d",&y[i],&x[i],&rad[i],&b[i]);
  59.    
  60.     int ret=-1; int col=0;
  61.  
  62.     for (int i=1;i<=n;i++) {
  63.         int sum=0;
  64.         vector<pair<pair<int,int>,int > > left,right;
  65.         for (int j=0;j<k;j++) {
  66.             pair<int,int> ret = getBounds(i,j);
  67.             if (ret.first==-1) continue;
  68.             left.push_back(make_pair(make_pair(ret.first,ret.second),b[j]));
  69.             right.push_back(make_pair(make_pair(ret.second,ret.first),b[j]));
  70.         }
  71.         sort(left.begin(),left.end());
  72.         sort(right.begin(),right.end());
  73.         int l1=0,r1=0;
  74.         for (int v=1;v<=m;v++) {
  75.             while (l1<left.size() && left[l1].first.first<=v) {
  76.                 sum+=left[l1].second;
  77.                 l1++;
  78.             }
  79.             if (sum>ret) {
  80.                 ret=sum;
  81.                 col=1;
  82.             } else if (sum==ret) {
  83.                 col++;
  84.             }
  85.             while (r1<right.size() && right[r1].first.first<=v) {
  86.                 sum-=right[r1].second;
  87.                 r1++;
  88.             }
  89.         }
  90.     }
  91.     printf("%d\n%d",ret,col);
  92.     return 0;
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement