제출 #434399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434399		qwerasdfzxcl	Teams (IOI15_teams)	C++14	0 / 100	40 ms	8404 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
int a[101][101], S[101][101], N;

void init(int n, int A[], int B[]) {
    N = n;
    for (int i=0;i<n;i++) a[A[i]][B[i]]++;
    S[0][0] = a[0][0];
    for (int i=1;i<=n;i++) S[i][0] = S[i-1][0] + a[i][0];
    for (int j=1;j<=n;j++) S[0][j] = S[0][j-1] + a[0][j];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++) S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+a[i][j];
    }
    /*for (int i=0;i<=n;i++){
        for (int j=0;j<=n;j++) printf("%d ", S[i][j]);
        printf("\n");
    }*/
}

int can(int M, int K[]) {
    int s = 0;
    for (int i=0;i<M;i++) s += K[i];
    if (s>N) return 0;
    sort(K, K+M, greater<int>());
    int nxt = 0;
    for (int i=0;i<M;i++){
        int tmp1 = S[K[i]][N];
        if (K[i]) tmp1 -= S[K[i]][K[i]-1];
        assert(tmp1>=0);
        //printf("%d %d\n", K[i], tmp1);
        if (tmp1<K[i]+nxt) return 0;
        if (i<M-1){
            int tmp2 = S[K[i+1]][N];
            if (K[i]) tmp2 -= S[K[i+1]][K[i]-1];
            int tmp3 = tmp1-tmp2;
            if (tmp3<K[i]+nxt) nxt = K[i]+nxt-tmp3;
            else nxt = 0;
            assert(tmp2>=0 && tmp3>=0);
        }
    }
    return 1;
}

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