結果

問題 No.335 門松宝くじ
ユーザー nmnmnmnmnmnmnmnmnmnmnmnmnmnm
提出日時 2016-01-11 02:58:12
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,138 bytes
コンパイル時間 790 ms
コンパイル使用メモリ 93,804 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 18:43:08
合計ジャッジ時間 2,912 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
権限があれば一括ダウンロードができます

ソースコード

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<<9)
#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[303][303];
  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