제출 #345314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345314		mansur	결혼 문제 (IZhO14_marriage)	C++14	36 / 100	1597 ms	1804 KiB

marriage

#include<bits/stdc++.h>
using namespace std;
 
#define all(a) a.begin(),a.end()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define fix fixed<<setprecision
#define pii pair<int,int>
#define E exit (0)
#define int long long
const int inf=1e9;
map<int,bool>was;
map<int,vector<int>>s;
int n,m,k;
bool f(int pos,int l,int r) {
	if (pos==m+1) {
		return true;
	}
	bool ok=false;
	for (auto e:s[pos]) {
		if (was[e]==false&&e>=l&&e<=r) {
			was[e]=true;
			ok=max(ok,f(pos+1,l,r));
			was[e]=false;	
		}
	}
	return ok;
}
signed main() {
	//freopen("planting.in","r",stdin);
	//freopen("planting.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	srand(time(0));
	cin>>n>>m>>k;
	for (int i=1;i<=k;i++) {
		int a,b;
		cin>>a>>b;
		s[b].pb(a);
	}
	int ans=0;
	for (int i=1;i<=n;i++) {
		for (int j=i;j<=n;j++) {
			ans+=(f(1,i,j)==true?1:0);
				
		}
	}
	cout<<ans;
}         

• Subtask 1: 36 / 100