Submission #37927

#	Time	Username	Problem	Language	Result	Execution time	Memory
37927		Talant	Marriage questions (IZhO14_marriage)	C++14	30 / 100	53 ms	8272 KiB

marriage

#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)1e5 + 7;

int n,m,k;
int x,y;
int a[1001][1001];
int ans;

vector <int> g[N];

bool check (int l,int r) {
        if (m == 1) {
                for (int i = l; i <= r; i ++)
                        if (a[i][1])
                                return 1;
        }
        else if (m == 2) {
                for (int i = l; i <= r; i ++)
                        for (int j = l; j <= r; j ++)
                                if (i != j) {
                                        if (a[i][1] && a[j][2])
                                                return 1;

                                        if (a[i][2] && a[j][1])
                                                return 1;
                                }
        }
        else if (m == 3) {
                for (int i = l; i <= r; i ++)
                        for (int j = l; j <= r; j ++)
                                for (int o = l; o <= r; o ++) {
                                        vector <int> v;
                                        if (i != j && o != j && o != i) {
                                                v.pb(1),v.pb(2),v.pb(3);
                                                do {
                                                        if (a[i][v[0]] && a[j][v[1]] && a[o][v[2]])
                                                                return 1;
                                                }
                                                while(next_permutation(v.begin(),v.end()));
                                        }
                                }
        }
        else if (m == 4) {
                for (int i = l; i <= r; i ++)
                        for (int j = l; j <= r; j ++)
                                for (int o = l; o <= r; o ++)
                                        for (int u = l; u <= r; u ++) {
                                                vector <int> v;
                                                v.pb(1),v.pb(2),v.pb(3),v.pb(4);
                                                if (i != j && o != j && o != i && u != i && u != j && u != o) {
                                                        do {
                                                                if (a[i][v[0]] && a[j][v[1]] && a[o][v[2]] && a[u][v[3]])
                                                                        return 1;
                                                        }
                                                        while(next_permutation(v.begin(),v.end()));
                                                }
                                }
        }
        return false;
}
int main () {
        cin >> n >> m >> k;

        for (int i = 1; i <= k; i ++) {
                cin >> x >> y;
                a[x][y] = 1;
        }
        for (int i = 1; i <= n; i ++) {
                for (int j = i + m - 1; j <= n; j ++) {
                        if (check(i,j))
                                ans ++;
                }
        }
        cout << ans << endl;
}

• Subtask 1: 30 / 100