結果

問題 No.1645 AB's abs
コンテスト
ユーザー ramia777
提出日時 2022-05-21 18:51:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 2,000 ms
コード長 1,931 bytes
コンパイル時間 810 ms
コンパイル使用メモリ 95,136 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-09-20 12:03:49
合計ジャッジ時間 2,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

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