結果

問題 No.335 門松宝くじ
コンテスト
ユーザー nmnmnmnmnmnmnm
提出日時 2016-01-11 03:39:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,140 bytes
コンパイル時間 1,001 ms
コンパイル使用メモリ 92,436 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-09-19 18:43:15
合計ジャッジ時間 2,958 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 8 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))

#define MOD 1000000007

#define N_MAX (1<<10)
#define INF 1000000000000LL

int nn_mx;
long long dat_mx[(2 * N_MAX) - 1];

void init_mx(int n1){
  nn_mx = 1;

  while(nn_mx < n1)nn_mx *= 2;

  for(int i = 0; i < 2 * nn_mx - 1; i++){
    dat_mx[i] = -INF;
  }
}

void update_mx(int k, long long a){
  k += nn_mx - 1;
  dat_mx[k] = a;
  while(k > 0){
    k = (k - 1) / 2;
    dat_mx[k] = max(dat_mx[k * 2 + 1], dat_mx[k * 2 + 2]);
  }
}

long long query_mx(int a, int b, int k, int l, int r){
  if(r <= a || b <= l)return -INF;

  if(a <= l && r <= b){
    return dat_mx[k];
  }
  else{
    long long vl = query_mx(a, b, k * 2 + 1, l, (l + r) / 2);
    long long vr = query_mx(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl, vr);
  }
}

long long f(vector<int> v){
  int d[1005][1005];
  clr(d,0);
  init_mx(v.sz);
  rep(i,0,v.sz){
    update_mx(i,v[i]);
  }
  rep(i,0,v.sz){
    rep(j,i+1,v.sz){
      if(v[i]==v[j])continue;
      if(v[i]<v[j]){
        if(i>0){
          int a = query_mx(0,i,0,0,nn_mx);
          if(a>v[j]){
            d[min(v[i],v[j])][max(v[i],v[j])] = max(d[min(v[i],v[j])][max(v[i],v[j])],v[i]*v[j]*a);
            d[min(v[i],a)][max(v[i],a)] = max(d[min(v[i],a)][max(v[i],a)],v[i]*v[j]*a);
            d[min(a,v[j])][max(a,v[j])] = max(d[min(a,v[j])][max(a,v[j])],v[i]*v[j]*a);
          }
        }
      }
      else{
        if(j<v.sz-1){
          int a = query_mx(j+1,v.sz,0,0,nn_mx);
          if(a>v[i]){
            d[min(v[i],v[j])][max(v[i],v[j])] = max(d[min(v[i],v[j])][max(v[i],v[j])],v[i]*v[j]*a);
            d[min(v[i],a)][max(v[i],a)] = max(d[min(v[i],a)][max(v[i],a)],v[i]*v[j]*a);
            d[min(a,v[j])][max(a,v[j])] = max(d[min(a,v[j])][max(a,v[j])],v[i]*v[j]*a);
          }
        }
      }
      if(j>i+1){
        int a = query_mx(i+1,j,0,0,nn_mx);
        if(a>max(v[i],v[j])){
            d[min(v[i],v[j])][max(v[i],v[j])] = max(d[min(v[i],v[j])][max(v[i],v[j])],v[i]*v[j]*a);
            d[min(v[i],a)][max(v[i],a)] = max(d[min(v[i],a)][max(v[i],a)],v[i]*v[j]*a);
            d[min(a,v[j])][max(a,v[j])] = max(d[min(a,v[j])][max(a,v[j])],v[i]*v[j]*a);
        }
      }
    }
  }
  long long ret = 0;
  rep(i,1,v.sz+1){
    rep(j,i+1,v.sz+1){
      ret += 1LL*d[i][j];
    }
  }
  return ret;
}

int main(){
  int n,m;
  cin>>n>>m;
  long long mx = 0;
  int index = 0;
  rep(i,0,m){
    vector<int> v;
    rep(j,0,n){
      int a;
      cin>>a;
      v.pb(a);
    }
    long long b = f(v);
    if(b>mx){
      mx = b;
      index = i;
    }
  }
  cout << index << endl;
  return 0;
}
0