fork(2) download
copy 
  1. #include<bits/stdc++.h>
  2. #define db double
  3. #define fs first
  4. #define sc second
  5. #define maxn 1005
  6. #define ll long long
  7. using namespace std;
  8. int n,k,d[maxn],sum[maxn];
  9. struct data
  10. {
  11.             ll s;
  12.             int c;
  13. };
  14. data a[maxn];
  15. ll res;
  16. typedef pair<int,int> II;
  17. II c[maxn][maxn];
  18. void tinh(int k)
  19. {
  20.             d[k]++;
  21.             c[k][d[k]].fs=c[k][1].fs;
  22.             c[k][d[k]].sc=c[k][1].sc;
  23.             for (int i=2; i<=d[k]; ++i)
  24.             {
  25.                         a[k].s+=((ll)(c[k][i].fs-c[k][i-1].fs)*(c[k][i].sc+c[k][i-1].sc));
  26.             }
  27.             if (a[k].s<0) a[k].s=-a[k].s;
  28. }
  29. bool cmp(const data &a,const data &b)
  30. {
  31.             return a.s<b.s;
  32. }
  33. int main()
  34. {
  35.             //freopen("TFIELD.inp","r",stdin);
  36.             ios::sync_with_stdio(0);
  37.             cin.tie(0);
  38.             cout.tie(0);
  39.             cin>>n>>k;
  40.             for (int i=1; i<=n; ++i)
  41.             {
  42.                         cin>>d[i]>>a[i].c;
  43.                         for (int j=1; j<=d[i]; ++j)
  44.                                     cin>>c[i][j].fs>>c[i][j].sc;
  45.             }
  46.             for (int i=1; i<=n; ++i) tinh(i);
  47.             sort(a+1,a+n+1,cmp);
  48.             sum[n+1]=1000000000;
  49.             for (int i=1; i<=n; ++i)
  50.             {
  51.                         sum[0]=0;
  52.                         for (int j=1; j<=n; ++j)
  53.                                     if (a[j].c!=i) sum[j]=sum[j-1]+1;
  54.                                     else sum[j]=sum[j-1];
  55.                         int r=1;
  56.                         for (int l=1;l<=n;++l)
  57.                         {
  58.                                     while(sum[r+1]-sum[l-1]<=k)
  59.                                                 ++r;
  60.                                     res=max(res,a[r].s-a[l-1].s);
  61.                         }
  62.             }
  63.             cout<<res/2;
  64.             if (res%2) cout<<".5";
  65.             else cout<<".0";
  66.             return 0;
  67. }
  68.  
Success #stdin #stdout 0s 23152KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0
https://ideone.com/twDbdE
problem TFIELD, based on SPOJ submission 19982469 (CPP14), 2017-08-16 16:57:25
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!