結果

問題 No.335 門松宝くじ
コンテスト
ユーザー nmnmnmnmnmnmnm
提出日時 2016-01-11 11:18:14
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 423 ms / 2,000 ms
コード長 3,844 bytes
コンパイル時間 711 ms
コンパイル使用メモリ 93,104 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-09-19 18:45:27
合計ジャッジ時間 4,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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_mn;
long long dat_mn[(2 * N_MAX) - 1];

void init_mn(int n1){
  nn_mn = 1;

  while(nn_mn < n1)nn_mn *= 2;

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

void update_mn(int k, long long a){
  k += nn_mn - 1;
  dat_mn[k] = a;
  while(k > 0){
    k = (k - 1) / 2;
    dat_mn[k] = min(dat_mn[k * 2 + 1], dat_mn[k * 2 + 2]);
  }
}

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

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

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);
  }
}

int f(vector<int> v){
  int d[1005][1005];
  clr(d,0);
  init_mx(v.sz);
  init_mn(v.sz);
  rep(i,0,v.sz){
    update_mx(i,v[i]);
    update_mn(i,v[i]);
  }
  rep(i,0,v.sz){
    rep(j,i+1,v.sz){
      if(v[i]<v[j]){
        if(i>0){
          int a = query_mx(0,i,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])],max(a,v[j]));
          }
        }
        if(j<v.sz-1){
          int a = query_mn(j+1,v.sz,0,0,nn_mn);
          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[j]);
          }
        }
      }
      else{
        if(i>0){
          int a = query_mn(0,i,0,0,nn_mn);
          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]);
          }
        }
        if(j<v.sz-1){
          int a = query_mx(j+1,v.sz,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])],max(a,v[i]));
          }
        }
      }
      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])],a);
        }
        int b = query_mn(i+1,j,0,0,nn_mn);
        if(b<min(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])],max(v[i],v[j]));
        }
      }
    }
  }
  int ret = 0;
  rep(i,1,v.sz+1){
    rep(j,i+1,v.sz+1){
      ret += 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