존못코딩

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
 
vector <int> back;
vector <vector <int> >vec;
vector <bool> chk;
char a[2][501][5];
 
bool bip(int v)
{
    int u;
    for (int i = 0; i < vec[v].size(); i++)
    {
        u = vec[v][i];
        if (chk[u])continue;
        chk[u] = true;
        if (back[u] == -1 || bip(back[u]))
        {
            back[u] = v;
            return true;
        }
    }
    return false;
 
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int c, d, v;
        scanf("%d %d %d", &c, &d, &v);
        vec = vector <vector <int> >(v + 1);
        back = vector <int>(v+1, -1);
        for (int i = 0; i < v; i++) {
            scanf("%s %s", a[0][i], a[1][i]);
        }
        for (int i = 0; i < v-1; i++) {
            for (int j = i + 1; j < v; j++) {
                if (!strcmp(a[0][i], a[1][j]) || !strcmp(a[1][i], a[0][j])) {
                    if (a[0][i][0] == 'C')vec[i].push_back(j);
                    else vec[j].push_back(i);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < v; i++) {
            chk = vector <bool>(v + 1, false);
            if (bip(i))ans++;
        }
        printf("%d\n", v-ans);
    }
 
    return 0;
}

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <memory.h>
using namespace std;
 
#define ll long long
 
ll dp[11][11][11][11][11][6][6];
int cnt[6], n, s;

ll dy(int a, int b, int c, int d, int e, int pre, int ppre)
{
	if (a + b + c + d + e == s)return 1;
	ll &ret = dp[a][b][c][d][e][pre][ppre];
	if (ret != -1)return ret;

	ret = 0;

	if (cnt[1] > a && pre != 1 && ppre != 1)ret += dy(a + 1, b, c, d, e, 1, pre);
	if (cnt[2] > b&& pre != 2 && ppre != 2)ret += dy(a, b + 1, c, d, e, 2, pre);
	if (cnt[3] > c&& pre != 3 && ppre != 3)ret += dy(a, b, c + 1, d, e, 3, pre);
	if (cnt[4] > d&& pre != 4 && ppre != 4)ret += dy(a, b, c, d + 1, e, 4, pre);
	if (cnt[5] > e&& pre != 5 && ppre != 5)ret += dy(a, b, c, d, e + 1, 5, pre);

	return ret;
}

int main()
{
	scanf("%d", &n); 
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cnt[i]);
		s += cnt[i];
	}
	memset(dp, 0xff, sizeof(dp));
	printf("%lld\n", dy(0, 0, 0, 0, 0, 0, 0));
} 

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <memory.h>
using namespace std;
  
int n, m;
int a[502][502];
int dp[502][502];
  
const int ud[4] = { -1,1,0,0 };
const int lr[4] = { 0,0,-1,1 };
  
int dy(int i, int j)
{
    int &ret = dp[i][j];
    if (ret != -1)return ret;
    ret = 0;
    for (int w = 0; w < 4; w++) {
        int x = i + ud[w], y = j + lr[w];
        if (x < 1 || x>n || y<1 || y>n)continue;
        if (a[i][j] > a[x][y])ret = max(ret, 1 + dy(x, y));
    }
    return ret = (ret == 0 ? 1 : ret);
}
int main()
{
    int M = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)scanf("%d", &a[i][j]);
    memset(dp, 0xff, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (dp[i][j] == -1)M = max(M, dy(i, j));
        }
    printf("%d\n", M);
}

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <memory.h>

#define MAX 987654321
#define ll long long
using namespace std;
struct MCMF
{
	int totalflow, totalcost, V;
	vector <vector <int> > flow, vec, capacity, cost;
	MCMF(int n) : V(n), totalcost(0), totalflow(0)
	{
		capacity = cost = flow = vector<vector <int> >(V, vector<int>(V, 0));
		vec = vector <vector <int> >(n);
	}

	void addedge(int a, int b, int co, int cap)
	{
		vec[a].push_back(b);
		this->cost[a][b] = co;
		this->capacity[a][b] = cap;
	}

	int excute(int S, int E) // SPFA algorithm
	{
		int a, b;
		vector <int> dist(V, MAX);
		vector <int> parent(V, -1);
		vector <bool> chk(V, false);
		queue <int> que;
		dist[S] = 0;
		que.push(S);
		while (!que.empty())
		{
			a = que.front(); que.pop();
			chk[a] = false;
			for (int i = 0; i < vec[a].size(); i++)
			{
				b = vec[a][i];
				if (capacity[a][b] - flow[a][b] > 0 && (dist[b] >= MAX || dist[b] > dist[a] + cost[a][b]))
				{
					dist[b] = dist[a] + cost[a][b];
					parent[b] = a;
					if (!chk[b])
					{
						chk[b] = true;
						que.push(b);
					}
				}

			}
		}
		if (dist[E] < MAX)
		{
			// if (dist[E] > 0)return MAX;
			totalcost += dist[E];
			totalflow++;
			for (int v = E; v != S; v = parent[v])
			{
				flow[parent[v]][v] += 1;
				flow[v][parent[v]] -= 1;
			}
		}
		return dist[E];
	}
};
struct dot {
	int a, b, c, d, cost;
	dot() {}
	dot(int a, int  b, int c, int d, int cost) :a(a), b(b), c(c), d(d), cost(cost) {}
};

int main()
{
	int t, n, m;
	scanf("%d", &t);
	while (t--)
	{
		int a, b, c, d, e;
		scanf("%d %d", &n, &m);
		vector <dot> R, C;
		for (int i = 0; i < n; i++) {
			scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
			if (c < a)swap(a, c);
			R.emplace_back(a, b, c, d, e);
		}
		for (int i = 0; i < m; i++) {
			scanf("%d %d %d %d %d", &a, &b, &c, &d, &e);
			if (d < b)swap(b, d);
			C.emplace_back(a, b, c, d, e);
		}
		MCMF mcmf(n + m + 2);
		int S = 0, E = n + m + 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (R[i].a <= C[j].a && C[j].a <= R[i].c && C[j].b <= R[i].b && R[i].b <= C[j].d) {
					mcmf.addedge(i + 1, n + j + 1, -R[i].cost*C[j].cost, 1);
					mcmf.addedge(n + j + 1, i + 1, R[i].cost*C[j].cost, 0);
				}
			}
		}
		for (int i = 0; i < n; i++) {
			mcmf.addedge(S, i + 1, 0, 1);
			mcmf.addedge(i + 1, S, 0, 0);
		}
		for (int i = 0; i < m; i++) {
			mcmf.addedge(n + i + 1, E, 0, 1);
			mcmf.addedge(E, n + i + 1, 0, 0);
		}
		while (mcmf.excute(S, E) < MAX) {}
		printf("%d %d\n", mcmf.totalflow, -mcmf.totalcost);
	}
}

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stdlib.h>;
using namespace std;
#define ll long long
int h;
struct dot {
	int l, r,id;
	bool operator<(const dot&A)const {
		return l / h == A.l / h ? r < A.r : l / h < A.l / h;
	}
}query[100001];
ll res[100001];
int cnt[1000001];
ll move(int t, int val) { cnt[val] += t; return ((ll)2 * (ll)t*(ll)cnt[val] - 1)*(ll)val; }
/*
   long long int moce(int t,int val)
   개수가 변화 할 때마다, 제곱의 값은 0 1 4 9 16 25.... 로 그  차이가 1,3,5,7,9로 발생한다. 
    즉, 개수-1개 값의 변화가 일어나므로, 2*cnt*k (k=1,-1) 라는 함수로 만들어 낼 수 있다. 
*/

int main()
{
	int n, k, l, r;
	scanf("%d %d", &n, &k);
	h = sqrt(n);
	vector <ll>a(n + 1,0);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &query[i].l, &query[i].r);
		query[i].id = i;
	}sort(query, query + k);

	ll sum = 0;
	l = query[0].l, r = query[0].r;
	for (int i = l; i <= r; i++)sum += move(1, a[i]);
	res[query[0].id] = sum;

	for (int i = 1; i < k; i++)
	{
		while (l > query[i].l)sum += move(1, a[--l]);
		while (l < query[i].l)sum += move(-1, a[l++]);
		while (r > query[i].r)sum += move(-1, a[r--]);
		while (r < query[i].r)sum += move(1, a[++r]);
		res[query[i].id] = sum;
	}
	for (int i = 0; i < k; i++)printf("%lld\n", res[i]);
	return 0;
}

#include <stdio.h>
using namespace std;
const int ud[4] = { 0,0,1,-1 };
const int lr[4] = { -1,1,0,0 };
char ary[5][6];
int res;
bool chk[1 << 25];
void dfs(int cnt, int scnt,int stat)
{
    chk[stat] = true;
    if (cnt >= 7) {
        if (scnt >= 4)res++;
        return;
    }
    for (int i = 0; i < 25; i++) {
        if (!(stat&(1 << i)))continue;
        int x = i / 5, y = i % 5;
        for (int w = 0; w < 4; w++) {
            int _x = x + ud[w], _y = y + lr[w];
            if (_x < 0 || _x > 4 || _y < 0 || _y > 4)continue;
            if (stat&(1 <<(_x * 5 + _y)) || chk[stat|(1<<(_x*5+_y))])continue;
            dfs(cnt + 1, scnt + (ary[_x][_y] == 'S'), stat | (1 << (_x * 5 + _y)));
        }
    }
}
 
int main()
{
    for (int i = 0; i  <  5; i++)scanf("%s", ary[i]);
    for (int i = 0; i  <  5; i++)
        for (int j = 0; j  <  5; j++)
            dfs(1, ary[i][j] == 'S',(1<<(i*5+j)));
 
    printf("%d\n", res);
    return 0;
}