Submission #64948

#	Time	Username	Problem	Language	Result	Execution time	Memory
64948		mirbek01	Teams (IOI15_teams)	C++17	21 / 100	303 ms	21744 KiB

teams

#include "teams.h"
# include <bits/stdc++.h>

using namespace std;

int n, mt[100005], used[100005];
vector <int> a, b, g[100005];

void init(int N, int A[], int B[]) {
      n = N;
      for(int i = 0; i < n; i ++)
            a.push_back(A[i]), b.push_back(B[i]);
}

bool kuhn(int v){
      if(used[v]) return false;
      used[v] = 1;
      for(int to : g[v]){
            if(mt[to] == -1 || kuhn(mt[to])){
                  mt[to] = v;
                  return true;
            }
      }
      return false;
}

int can(int M, int K[]) {
      int sum = 0;
      for(int i = 0; i < M; i ++)
            sum += K[i];
      if(sum > n) return 0;
      for(int i = 0; i < n; i ++){
            int pref = 0;
            for(int j = 0; j < M; j ++){
                  if(a[i] <= K[j] && K[j] <= b[i]){
                        for(int k = pref; k < pref + K[j]; k ++){
                              g[i].push_back(k + n),
                              g[k + n].push_back(i);
                        }
                  }
                  pref += K[j];
            }
      }
      for(int i = 0; i <= n + sum; i ++)
            mt[i] = -1;
      for(int i = 0; i < n; i ++){
            memset(used, 0, sizeof(used));
            kuhn(i);
      }
      int ss = sum;
      for(int i = n; i < n + ss; i ++){
            if(mt[i] != -1) sum --;
      }
      for(int i = 0; i < n + ss; i ++)
            g[i].clear();
      if(!sum) return 1;
      return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23