結果

問題 No.335 門松宝くじ
コンテスト
ユーザー Hachimori
提出日時 2016-03-14 00:33:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 2,555 bytes
コンパイル時間 987 ms
コンパイル使用メモリ 71,016 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-25 11:42:46
合計ジャッジ時間 2,645 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void work()’:
main.cpp:101:13: warning: ‘maxType’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |     cout << maxType << endl;
      |             ^~~~~~~

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int TYPE = 3;
const int BUF = 805;


class SegTree{
public:
  int v[BUF*4];

  SegTree(){ 
    memset(v,0,sizeof(v));
  }
  
  int init(int node, int L, int R, int a[BUF]){
    if(L==R) return v[node] = a[L];
    int s = init(node*2+1,L,(L+R)/2,a);
    int t = init(node*2+2,(L+R)/2+1,R,a);
    return v[node] = max(s,t);
  }

  int get(int node, int L, int R, int LQ, int RQ){
    if(R<LQ || RQ<L) return -1;
    if(LQ<=L && R<=RQ) return v[node];
    int s = get(node*2+1,L,(L+R)/2,LQ,RQ);
    int t = get(node*2+2,(L+R)/2+1,R,LQ,RQ);
    return max(s,t);
  }
  
  int update(int node, int L, int R, int Q, int chVal){
    if(R<Q || Q<L) return v[node];
    if(L==R) return v[node] = chVal;
    int s = update(node*2+1,L,(L+R)/2,Q,chVal);
    int t = update(node*2+2,(L+R)/2+1,R,Q,chVal);
    return v[node] = max(s,t);
  }
};


int nVal, nType;
int v[TYPE][BUF];

void read() {
    cin >> nVal >> nType;
    for (int i = 0; i < nType; ++i) {
        for (int j = 0; j < nVal; ++j) {
            cin >> v[i][j];
        }
    }
}


void work() {
    int maxType;
    int maxSum = 0;

    for (int type = 0; type < nType; ++type) {
        SegTree segTree;
        segTree.init(0, 0, nVal - 1, v[type]);
        
        int sum = 0;
        for (int i = 0; i < nVal; ++i) {
            for (int j = i + 1; j < nVal; ++j) {
                int a = v[type][i];
                int b = v[type][j];

                int toAdd = max(a, b);
                
                // Have maximum value in the middle
                if (i + 1 != j) {
                    int midMax = segTree.get(0, 0, nVal - 1, i + 1, j - 1);
                    toAdd = max(toAdd, midMax);
                }

                // Have maximum value in the first / third
                if (a < b) {
                    if (i != 0) {
                        int fstMax = segTree.get(0, 0, nVal - 1, 0, i - 1);
                        toAdd = max(toAdd, fstMax);
                    }
                }
                else {
                    if (j != nVal - 1) {
                        int thrdMax = segTree.get(0, 0, nVal - 1, j + 1, nVal - 1);
                        toAdd = max(toAdd, thrdMax);
                    }
                }
                
                sum += toAdd;
            }
        }

        if (maxSum < sum) {
            maxSum = sum;
            maxType = type;
        }
    }

    cout << maxType << endl;
}


int main() {
    read();
    work();
    return 0;
}
0