Submission #36106424

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
typedef long long ll;
typedef __int128 lll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
ll C[1010];

// return t0/b0 < t1/b1
bool lt(pair<ll,ll> frac0,pair<ll,ll>frac1){ // less than
  auto [t0,b0]=frac0;
  auto [t1,b1]=frac1;
  assert(b0!=0&&b1!=0);
  if(b0<0){
    t0*=-1;
    b0*=-1;
  }
  if(b1<0){
    t1*=-1;
    b1*=-1;
  }
  return ((lll)t0)*b1 < ((lll)t1)*b0; // 估计不到范围 甩个128吧
}

bool great[1010][1010]; // great[i][j] : cx_i+y_i > cx_j+y_j
int incnt[1010]; // 入度

int main(){
  int n=read();
  int k=read();
  rep(i,0,n)C[i]=read();
  vector<pair<ll,ll>>xy; // {6e5,~36e10}
  rep(i,0,n){
    ll a=0; // fi'(1), alpha, 6e5
    ll b=0; // fi''(1) beta, 6e10
    rep(j,0,6){
      ll v=read();
      a+=v;
      b+=v*(v-1);
    }
    xy.push_back({a,6*a+6*b-a*a-36*C[i]}); // {6e5, ~36e10}
  }
  // c=-infinity
  rep(i,0,n)rep(j,i+1,n){
    auto [xi,yi]=xy[i];
    auto [xj,yj]=xy[j];
    if(xi==xj){ // 不受c影响
      if(yi==yj){ // 完全相等 用index比大小
        great[j][i] = true;
        incnt[i]++;
      }else if(yi<yj){
        great[j][i] = true;
        incnt[i]++;
      }else{
        great[i][j] = true;
        incnt[j]++;
      }
    }else{ // c负无限大且x不想等时 不受y 影响, xi c < xj c  则 xi > xj
      if(xi < xj){ // xic > xjc
        great[i][j] = true;
        incnt[j]++;
      }else{
        great[j][i] = true;
        incnt[i]++;
      }
    }
  }
  ll Sx=0; // 1000 * 6e5 = 6e8
  ll Sy=0; // 1000 * ~36e10 = ~36e13
  auto add=[&](int idx,int t=1){
    Sx+=t*xy[idx].first;
    Sy+=t*xy[idx].second;
  };
  rep(i,0,n) if(incnt[i]<k) add(i);
  ll ans=Sx*Sx+Sy; // 72e13
  vector<pair<pair<ll,ll>,pair<int,int>> > c; // 记录每次翻转的, {{~36e10,12e5},{1e5,1e5}}
  rep(i,0,n)rep(j,i+1,n){
    auto [xi,yi]=xy[i];
    auto [xj,yj]=xy[j]; // c=(yj-yi)/(xi-xj)
    if(xi==xj)continue;
    c.push_back({{yj-yi,xi-xj},{i,j}});
  }
  sort(c.begin(),c.end(),[](auto&v0,auto&v1){return lt(v0.first,v1.first);});
  vector<vector<pair<int,int>>> ijs; // 同斜率合并
  rep(i,0,c.size()){
    if(i==0||lt(c[i-1].first,c[i].first)){
      ijs.push_back({c[i].second});
    }else{
      ijs.back().push_back({c[i].second});
    }
  }
  for(auto ij:ijs){
    for(auto [i,j]:ij){
      if(great[j][i]) swap(i,j); // assert(i > j)
      great[i][j]=false; // 可以省略great的修改, 因为只有incnt真的参与计算, 之后swap也不会再有i,j
      if(incnt[j]--==k) add(j); // k => k-1 原来没j 现在有j
      great[j][i]=true;
      if(++incnt[i]==k) add(i,-1); // k-1 => k 原来有i 现在无i
    }
    ans=max(ans,Sx*Sx+Sy);
  }
  printf("%d\n",(mint(ans)/36).val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:8:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    8 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result