Cod sursa(job #1569706)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 15 ianuarie 2016 20:57:45
Problema Drumuri minime Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 1000000009
#define NMAX 100005
#define MMAX 5005
#define INF (1<<30)
#define mp make_pair

using namespace std;

FILE *fin = freopen("monezi2.in", "r", stdin);
FILE *fout = freopen("monezi2.out", "w", stdout);

typedef pair<int, int> pii;

int s[NMAX], dp[2][NMAX];

int main() {
	int n, i, nr,j;

	cin >> n;
	for (i = 1; i <= n; ++i) {
		cin >> nr;

		s[i] = s[i - 1] + nr;
	}

	dp[0][0] = 1;
	for (i = 1; i <= n; ++i) {
		dp[i%2][s[i]] = 1;
		for (j = 0; j <= NMAX; ++j) {
			if (dp[(i + 1)%2][j] == 1 || dp[i%2][j - s[i]] == 1 && j>s[i])
				dp[i%2][j] = 1;
		}
	}

	int Q;
	cin >> Q;
	for (i = 0; i < Q; ++i) {
		cin >> nr;
		if (dp[n % 2][nr])
			cout << "DA\n";
		else
			cout << "NU\n";
	}

	return 0;
}