結果

問題 No.335 門松宝くじ
コンテスト
ユーザー Kmcode1
提出日時 2016-01-15 23:39:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 44 ms / 2,000 ms
コード長 2,287 bytes
コンパイル時間 863 ms
コンパイル使用メモリ 95,956 KB
実行使用メモリ 8,424 KB
最終ジャッジ日時 2024-09-19 19:33:47
合計ジャッジ時間 1,695 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In constructor ‘st::st()’:
main.cpp:58:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |                         scanf("%d", &a);
      |                         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
using namespace std;

int n;
int m;
#define MAX 812
int ich[MAX];
int bit[MAX];
void add(int i, int x){
	i++;
	while (i < MAX){
		bit[i] = max(bit[i],x);
		i += i&-i;
	}
}
int sum(int i){
	int r = 0;
	i++;
	while (i){
		r = max(r,bit[i]);
		i -= i&-i;
	}
	return r;
}
long long int ss[MAX][MAX];

struct st{
	long long int score;
	vector<int> v;
	st(){
		memset(bit, 0, sizeof(bit));
		for (int i = 0; i < n; i++){
			int a;
			scanf("%d", &a);
			ich[a] = i;
			v.push_back(a);
		}
		score = 0;
		for (int i = 0; i < n; i++){
			for (int j = i + 1; j < n; j++){
				int a = v[i];
				int b = v[j];
				long long int add = 0;
				if (a > b){
					add = sum(a);
				}
				else{
					int k = sum(MAX - 3);
					if (k < a){

					}
					else{
						add = (long long int)(k);
					}
				}
				ss[i][j] = add;
			}
			add(v[i], v[i]);
		}
		memset(bit, 0, sizeof(bit));
		for (int i = n-1; i>=0; i--){
			for (int j = i - 1; j>=0; j--){
				swap(i, j);
				int a = v[i];
				int b = v[j];
				long long int add = 0;
				if (a < b){
					add = sum(a);
				}
				else{
					int k = sum(MAX - 3);
					if (k < b){

					}
					else{
						add = (long long int)(k);
					}
				}
				ss[i][j] = max(ss[i][j], add);
				swap(i, j);
			}
			add(v[i], v[i]);
		}
		for (int i = 0; i < n; i++){
			memset(bit, 0, sizeof(bit));
			for (int j = i + 1; j < n; j++){
				int a = v[i];
				int b = v[j];
				int mint = min(a, b);
				long long int add2 = sum(mint);
				int add3 = sum(MAX - 3);
				if (add3>max(a, b)){
					add2 = add3;
				}
				add2 = max(add2, ss[i][j]);
				score += add2;
				add(v[j], v[j]);
			}
		}
	}
};
int main(){
	cin >> n >> m;
	long long int best_score = 0;
	int idx = 0;
	for (int i = 0; i < m; i++){
		st *a = new st();
		if (a->score > best_score){
			idx = i;
			best_score = a->score;
		}
		delete a;
	}
	cout << idx << endl;
	return 0;
}
0