結果

問題 No.1645 AB's abs
ユーザー ramia777ramia777
提出日時 2022-05-21 18:51:39
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,931 bytes
コンパイル時間 791 ms
コンパイル使用メモリ 93,912 KB
実行使用メモリ 20,056 KB
最終ジャッジ日時 2023-10-20 16:31:30
合計ジャッジ時間 2,801 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 3 ms
7,768 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
5,716 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 4 ms
9,812 KB
testcase_09 AC 4 ms
9,816 KB
testcase_10 AC 4 ms
9,812 KB
testcase_11 AC 4 ms
9,812 KB
testcase_12 AC 4 ms
9,808 KB
testcase_13 AC 8 ms
20,048 KB
testcase_14 AC 7 ms
18,000 KB
testcase_15 AC 7 ms
20,052 KB
testcase_16 AC 7 ms
18,004 KB
testcase_17 AC 8 ms
20,048 KB
testcase_18 AC 7 ms
18,004 KB
testcase_19 AC 8 ms
20,052 KB
testcase_20 AC 7 ms
18,000 KB
testcase_21 AC 8 ms
18,000 KB
testcase_22 AC 8 ms
20,052 KB
testcase_23 AC 8 ms
20,052 KB
testcase_24 AC 8 ms
20,048 KB
testcase_25 AC 7 ms
20,052 KB
testcase_26 AC 8 ms
20,048 KB
testcase_27 AC 8 ms
20,052 KB
testcase_28 AC 8 ms
20,052 KB
testcase_29 AC 8 ms
20,052 KB
testcase_30 AC 8 ms
20,056 KB
testcase_31 AC 8 ms
20,052 KB
testcase_32 AC 8 ms
20,052 KB
testcase_33 AC 8 ms
20,052 KB
testcase_34 AC 8 ms
20,052 KB
testcase_35 AC 8 ms
20,052 KB
testcase_36 AC 8 ms
20,052 KB
testcase_37 AC 8 ms
20,052 KB
testcase_38 AC 7 ms
20,052 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//
// Yukicoder
// No.1645 AB's ABS 
//
//





//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <list>//list
#include <set> //tree
#include <map> //連想配列
#include <unordered_set> //hash
#include <unordered_map> //hash
#include <algorithm>
#include <iomanip>
#include <string>
#include <stdlib.h>

using namespace std;
typedef unsigned long long ULL;
typedef signed long long SLL;
typedef unsigned int UINT;


#define START (0)
#define RIGHT (1)
#define UP    (2)
#define LEFT  (3)
#define DOWN  (4)

#define DATA_MAX (1000000)
#define FMAX(a,b)  ((a)>(b)?(a):(b))
#define FMIN(a,b)  ((a)<(b)?(a):(b))


vector <vector <SLL>> memo2;//二次元可変配列

vector<SLL> memo1;
vector<SLL> c;
vector<SLL> v;
vector<SLL> dp;


SLL N;
ULL Result;




#define MOD 998244353

ULL memo[110][20100];
int a[100];


int main(int argc, char *argv[])
{
	
	//Nの値は1~100
	//数列の絶対値の値は-10000~10000
	//つまり100x20000のメモがあればOK
	//memo2.resize(110,vector<SLL>(20100));	//二次元可変配列の初期化



	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> a[i];
	}


	//最初の数字を＋する側だけ求める（全体の半分の合計を求める）
	memo[0][a[0]+10000] = 1;

	//2番目の数字から最後（N-1）の数字まで繰り返す
	for (int i = 1; i < N; i++)
	{
		for (int j=-10000;j<=10000;j++)
		{
			if (memo[i - 1][j + 10000])
			{
				int c;

				 c = a[i] + j;
				 memo[i][c + 10000] += memo[i - 1][j + 10000] % MOD;

				 c = -a[i] + j;
				 memo[i][c + 10000] += memo[i - 1][j + 10000] % MOD;
			}
		}
	}


	for (int j = -10000; j <= 10000; j++)
	{
		if (memo[N - 1][j + 10000])
		{
			Result +=  ( memo[N - 1][j + 10000]*abs(j));
			//cout << "RE=" << Result << ", m=" << memo[N - 1][j + 10000] << ", j=" << j << ",N=" << _fdebug<<endl;
		}
			
	}

	cout <<  (Result<<1) % MOD << endl;


	//getchar();
	

	return 0; //end
}
0