結果

問題 No.335 門松宝くじ
ユーザー HachimoriHachimori
提出日時 2016-03-14 00:33:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 134 ms / 2,000 ms
コード長 2,555 bytes
コンパイル時間 1,071 ms
コンパイル使用メモリ 72,188 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-26 03:49:54
合計ジャッジ時間 3,064 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 33 ms
4,348 KB
testcase_06 AC 49 ms
4,348 KB
testcase_07 AC 90 ms
4,348 KB
testcase_08 AC 78 ms
4,348 KB
testcase_09 AC 133 ms
4,348 KB
testcase_10 AC 134 ms
4,348 KB
testcase_11 AC 132 ms
4,348 KB
testcase_12 AC 134 ms
4,348 KB
testcase_13 AC 133 ms
4,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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