#994986 (C++23) No.1144 Triangles

提出ソース

結果

問題	No.1144 Triangles
ユーザー	れび
提出日時	2024-07-14 11:41:22
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	8,574 bytes
コンパイル時間	4,087 ms
コンパイル使用メモリ	274,764 KB
実行使用メモリ	10,140 KB
最終ジャッジ日時	2024-07-14 11:41:31
合計ジャッジ時間	8,857 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 10,012 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	TLE	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define rep(i,t,n) for(long long i=t;i<n;i++)
#define rep2(i,A) for(auto &i:A)
#define Sort(a) sort(a.begin(),a.end())
#define rSort(a,n,m) sort(a.begin()+n,a.begin()+m+1)
#define Reverse(a) reverse(a.begin(),a.end())
#define rReverse(a,n,m) reverse(a.begin()+n,a.begin()+m+1)
#define MOD1 998244353
#define MOD2 1000000007
#define sign(i) -1*pow(-1,i)
#define vi(A,N,i)  vector<long long> A(N,i)
#define vd(A,N,i)  vector<double> A(N,i)
#define vc(A,N,i)  vector<char> A(N,i)
#define vs(A,N,i)  vector<string> A(N,i)
#define vb(A,N,i)  vector<bool> A(N,i)
#define vp(A,N,i)  vector<Pair> A(N,{i,i})
#define vvi(A,N,M,i) vector<vector<long long>> A(N,vector<long long>(M,i))
#define vvp(A,N,M,i) vector<vector<Pair>> A(N,vector<Pair>(M,{i,i}))
#define vvd(A,N,M,i) vector<vector<double>> A(N,vector<double>(M,i))
#define vvc(A,N,M,i) vector<vector<char>> A(N,vector<char>(M,i))
#define vvb(A,N,M,i) vector<vector<bool>> A(N,vector<bool>(M,i))
#define vvs(A,N,M,i) vector<vector<string>> A(N,vector<string>(M,i))
#define vvvi(A,N,M,L,i) vector<vector<vector<ll>>> A(N,vector<vector<ll>>(M,vector<ll>(L,i)))
#define vvvs(A,N,M,L,i) vector<vector<vector<string>>> A(N,vector<vector<string>>(M,vector<string>(L,i)))
#define ll long long
#define INF ((1LL<<62)-(1LL<<31))
#define ALL(a) (a).begin(),(a).end()
//((a+b+c)-max(a,max(b,c))-min(a,min(b,c)))

//cout << fixed << setprecision(桁数);
using VVi=vector<vector<ll>>;
using Pair=pair<ll,ll>;
using graphi=vector<vector<ll>>;
using graphp=vector<vector<Pair>>;
struct Plane{
  ll x;
  ll y;
};
struct Path{
  ll cost;
  ll to;
};
template<typename T>
void CIN(vector<T> &A){
  rep(i,0,(ll)A.size()){
    cin>>A[i];
  }
  return;
}
struct ThreePlane{
  ll x,y,z;
  ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){}
  bool operator<(const ThreePlane& other) const {
    return x<other.x;
  }
  bool operator<=(const ThreePlane& other) const {
    return x<=other.x;
  }
  bool operator>(const ThreePlane& other) const {
    return x>other.x;
  }
  bool operator>=(const ThreePlane& other) const {
    return x>=other.x;
  }
};
struct FourPlane{
  ll dist;
  ll x;
  ll y;
  ll stat;
};
struct Fraction{
    ll p,q,r;
    Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){}
    bool operator<(const Fraction &other)const{
      if(p*other.q != other.p*q){
        return p*other.q < other.p*q;
      }else{
        return r>other.r;
      }
        
    }
};
struct Matrix{//正方のみ
  vector<vector<ll>> mat;
  Matrix(ll size):mat(vector<vector<ll>>(size,vector<ll>(size,0))){}
  void showerr(){
    rep2(i,mat){
      rep2(j,i)cerr<<j<<" ";
      cerr<<endl;
    }
    return;
  }
  void showout(){
    rep2(i,mat){
      rep2(j,i)cout<<j<<" ";
      cout<<endl;
    }
    return;
  }
};
template<typename T>
struct Zaatu{
  bool sorted;
  vector<T> za;
  Zaatu():sorted(false){}
  void add(T x){
    za.push_back(x);
    sorted=false;
  }
  void build(){
    sort(std::begin(za),std::end(za));
    sorted=true;
    za.erase(unique(std::begin(za),std::end(za)),std::end(za));
  }
  ll size(){
    if(!sorted)build();
    return (ll)za.size();
  }
  const T &operator[](int i){
    if(!sorted)build();
    return za[i];
  }
  ll get(const T &x){//x以上の最小値のindex
    if(!sorted)build();
    return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);
  }
  vector<ll> get(vector<T> mo){
    if(!sorted)build();
    vector<ll> result;
     transform(std::begin(mo),std::end(mo),back_inserter(result),[&](const T &x){
      return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);
    });
    return result;
  }
  typename vector<T>::iterator begin(){
    if(!sorted)build();
    return std::begin(za);
  }
  typename vector<T>::iterator end(){
    if(!sorted)build();
    return std::end(za);
  }
};

// ll POW(ll a,ll b,ll mod){
//   // ll c=1;
//   // a%=mod;
//   // while(b!=0){
//   //   if(b%2){
//   //     c*=a;
//   //     c%=mod;
//   //   }
//   //   a*=a;
//   //   a%=mod;
//   //   b/=2;
//   // }
//   return pow_mod(a,b,mod);
// }
ll GCD(ll a,ll b){
  if(b==0)return a;
  return GCD(b,a%b);
}
pair<long long, long long> extGCD(long long a, long long b) {// ax+by=1 solver
  if (b == 0) return make_pair(1, 0);
  long long x,y;
  tie(y,x)=extGCD(b,a%b);
  y-=a/b*x;
  return make_pair(x,y);
}
ll SQRT(ll a){
  ll low,high,mid;
  low=0;
  high=1LL<<31;
  while(high-low!=1){
    mid=(low+high)/2;
    if(mid*mid<=a){
      low=mid;
    }else{
      high=mid;
    }
  }
  return low;
}
string strmin(string x,string y){
  ll minlength=min((int)x.size(),(int)y.size());
  rep(i,0,minlength){
    if(x[i]>y[i])return y;
    if(x[i]<y[i])return x;
  }
  if((int)x.size()>(int)y.size())return y;
  return x;
}
ll LCS(string x,string y){
  ll xsize=(ll)x.size();
  ll ysize=(ll)y.size();
  vvi(dp,xsize+1,ysize+1,0);
  rep(i,1,xsize+1){
    rep(j,1,ysize+1){
      if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]);
      else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
    }
  }
  return dp[xsize][ysize];
}
ll Factorial(ll n,ll mod){
  ll a=1;
  if(n>=mod)return 0;
  rep(i,1,n+1){
    a*=i;
    a%=mod;
  }
  return a;
}
// ll Combination(ll n,ll k,ll mod){
//   if(n<k)return 0;
//   ll a=Factorial(n,mod);
//   ll b=inv_mod(Factorial(k,mod),mod);
//   ll c=inv_mod(Factorial(n-k,mod),mod);
//   a*=b;
//   a%=mod;
//   a*=c;
//   a%=mod;
//   return a;
// }
vector<pair<char,long long>> RLE(string x,char s=' ',long long a=0,vector<pair<char,long long>> res={}){
  for(auto i:x){
    if(s==i){
      a++;
    }else{
      if(s!=' ')res.push_back({s,a});
      s=i,a=1;
    }
  }
  res.push_back({s,a});
  return res;
}
vector<ll> cu1d(vector<ll> A){
  ll cu1=A.size();
  vector<ll> res(cu1+1,0);
  rep(i,0,cu1)res[i+1]=A[i];
  rep(i,1,cu1+1)res[i]+=res[i-1];
  return res;
}
vector<vector<ll>> cu2d(vector<vector<ll>> A){
  ll cu1=A.size(),cu2=A[0].size();
  vector<vector<ll>> res(cu1+1,vector<ll>(cu2+1,0));
  rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j];
  rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j];
  rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1];
  return res;
}
ll LIS(vector<ll> A){
  ll a=(ll)A.size();
  vector<ll> result(a,INF);
  ll answer=0;
  rep(i,0,a){
    ll ok=-1;
    ll ng=a;
    while(ng-ok!=1){
      ll mid=(ok+ng)/2;
      if(A[i]<=result[mid])ng=mid;
      else ok=mid;
    }
    result[ok+1]=A[i];
    answer=max(answer,ok+2);
  }
  return answer;
}
vector<ll> zaatu(vector<ll> A){
  vector<ll> B=A;
  Sort(B);
  B.erase(unique(ALL(B)),end(B));
  vector<ll> res;
   transform(ALL(A),back_inserter(res),[&](const ll &x){
    return lower_bound(ALL(B),x)-begin(B);
  });
  return res;
}
vector<string> trim(vector<string> A){
  bool frag=0;
  char s='#';
  ll h=(ll)A.size();
  ll w=(ll)A[0].size();
  ll a=-1,b=h,c=-1,d=w;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;
    if(frag)break;
    a=i;
  }
  frag=0;
  for(ll i=h-1;i>=0;i--){
    for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;
    if(frag)break;
    b=i;
  }
  frag=0;
  for(ll i=0;i<w;i++){
    for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;
    if(frag)break;
    c=i;
  }
  frag=0;
  for(ll i=w-1;i>=0;i--){
    for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;
    if(frag)break;
    d=i;
  }
  vector<string> B(b-a-1,"");
  for(ll i=a+1;i<b;i++)for(ll j=c+1;j<d;j++)B[i-a-1]+=A[i][j];
  return B;
}
char to_upper(char &s){
  if('a'<=s){
    s-=32;
  }
  return s;
}
char to_lower(char &s){
  if(s<='Z'){
    s+=32;
  }
  return s;
}
vector<vector<ll>> Warshall(vector<vector<ll>> A){
  ll a=A.size();
  rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
  return A;
}

ll bit_ceil(ll n) {
    ll x = 1;
    while (x < (ll)(n)) x *= 2;
    return x;
}
vector<string> make_grid(ll H,ll W,char filler='#'){
  vector<string> res(H+2);
  string st="";
  rep(i,0,W+2)st+=filler;
  res[0]=res[H+1]=st;
  string st2;
  rep(i,1,H+1){
    cin>>st2;
    res[i]=filler+st2+filler;
  }
  return res;
}



//Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
long long a,b,c,d,e,f,g,h,ans=0;
string w,x="",y="",z="";
char s,t,u;
bool frag=false,frag1=false,frag2=false;
vector<ll> X={1,0,-1,0},Y={0,1,0,-1};

int main(){
  cin>>a;
  vp(A,a,0);
  rep(i,0,a){
  	cin>>A[i].first>>A[i].second;
  }
  ans=0;
  rep(i,0,a-2){
  	rep(j,i+1,a-1){
	  	rep(k,j+1,a){
	  		ans+=abs((A[k].first-A[i].first)*(A[j].second-A[i].second)-(A[j].first-A[i].first)*(A[k].second-A[i].second));
	  		ans%=MOD2;
	  	}
  	}
  }
  cout<<ans<<endl;
}

yukicoder

結果

テストケース

ソースコード