Submission #541153

#	Time	Username	Problem	Language	Result	Execution time	Memory
541153		mosiashvililuka	Teams (IOI15_teams)	C++14	21 / 100	4034 ms	12784 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[500009],dp[500009],k[500009];
pair <int, int> p[500009];
void init(int Nn, int Aa[], int Bb[]) {
	b=Nn;
	for(i=1; i<=b; i++){
		p[i].first=Aa[i-1];p[i].second=Bb[i-1];
		k[p[i].first]++;k[p[i].second+1]--;
	}
	for(i=1; i<=b; i++) k[i]+=k[i-1];
}
int cost(int q, int w){
	int qw=0;
	for(int h=1; h<=b; h++){
		if(p[h].first<=q&&w<=p[h].second) qw++;
	}
	return qw;
}
int can(int Mm, int Kk[]) {
	a=Mm;zx=0;
	for(i=1; i<=a; i++){
		f[i]=Kk[i-1];zx+=f[i];
	}
	sort(f+1,f+a+1);
	if(zx>b){
		return 0;
	}
	dp[0]=0;
	for(i=1; i<=a; i++){
		zx=0;
		for(j=i-1; j>=1; j--){
			zx=min(zx,(dp[j]-cost(f[j],f[i])));
		}
		dp[i]=zx+k[f[i]]-f[i];
	}
	zx=0;
	for(i=1; i<=a; i++){
		zx=min(zx,dp[i]);
	}
	if(zx<0) return 0;
	return 1;
}

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