Submission #21794

#	Time	Username	Problem	Language	Result	Execution time	Memory
21794		sbansalcs	Teams (IOI15_teams)	C++14	21 / 100	4000 ms	13744 KiB

teams

#include "teams.h"
#include <stack>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
using namespace std;
const int N = 5e5+5;

int A[N],B[N];
int n;
int del[N];
int sz=0;
int dp[N];
void init(int _n, int a[], int b[]) {
	n=_n;
	for(int i=1;i<=n;i++)	{
		A[i]=a[i-1];
		B[i]=b[i-1];
	}
}

// int getUnder(int k, int y)	{

// 	int tot=0;
// 	for(int i=1;i<=n;i++)	{
// 		if(A[i]<=k && B[i]>=k)	tot++;
// 	}

// 	for(int i=sz;i>=1;i--)	{
		
// 	}
// }

// bool fx(int k)	{



// 	return 1;
// }

int getCount(int a, int b)	{
	int tot=0;
	for(int i=1;i<=n;i++)	{
		if(A[i]>a && A[i]<=b && B[i]>=b)	tot++;
	}
	return tot;
}

int can(int M, int K[]) {
	sort(K,K+M);
	vector<pair<int,int>> vt;
	for(int i=0;i<M;i++)	{
		if(vt.size()==0 || vt[vt.size()-1].first!=K[i])	{
			vt.push_back({K[i],1});
		}
		else	{
			vt[vt.size()-1].second++;
		}
	}
	int n2 = vt.size();
	int h=sqrt(n);
	assert(n2<=3*h);
	int mini=0;
	for(int i=0;i<n2;i++)	{
		dp[i]=getCount(0,vt[i].first)-vt[i].first*vt[i].second;
		for(int j=0;j<i;j++)	{
			dp[i]=min(dp[i],dp[j]-vt[i].first*vt[i].second+getCount(vt[j].first,vt[i].first));
		}
		if(dp[i]<0)	return 0;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:63:19: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
  int n2 = vt.size();
                   ^
teams.cpp:64:14: warning: conversion to 'int' from '__gnu_cxx::__enable_if<true, double>::__type {aka double}' may alter its value [-Wfloat-conversion]
  int h=sqrt(n);
              ^
teams.cpp:66:6: warning: unused variable 'mini' [-Wunused-variable]
  int mini=0;
      ^

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