oj.uz

Submission #21793

# Submission time Handle Problem Language Result Execution time Memory
21793 2017-04-25T20:46:51 Z sbansalcs Teams (IOI15_teams) C++14
21 / 100
 4000 ms 13728 KB 

#include "teams.h"
#include <stack>
#include <vector>
#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 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

teams.cpp: In function 'int can(int, int*)':
teams.cpp:61: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:62:6: warning: unused variable 'mini' [-Wunused-variable]
  int mini=0;
      ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8988 KB Output is correct
2 Correct 0 ms 8988 KB Output is correct
3 Correct 0 ms 8988 KB Output is correct
4 Correct 0 ms 8988 KB Output is correct
5 Correct 0 ms 8988 KB Output is correct
6 Correct 0 ms 8988 KB Output is correct
7 Correct 3 ms 8988 KB Output is correct
8 Correct 0 ms 8988 KB Output is correct
9 Correct 0 ms 8988 KB Output is correct
10 Correct 0 ms 8988 KB Output is correct
11 Correct 0 ms 8988 KB Output is correct
12 Correct 0 ms 8988 KB Output is correct
13 Correct 0 ms 8988 KB Output is correct
14 Correct 0 ms 8988 KB Output is correct
15 Correct 0 ms 8988 KB Output is correct
16 Correct 0 ms 8988 KB Output is correct
17 Correct 0 ms 8988 KB Output is correct
18 Correct 0 ms 8988 KB Output is correct
19 Correct 0 ms 8988 KB Output is correct
20 Correct 0 ms 8988 KB Output is correct
21 Correct 0 ms 8988 KB Output is correct
22 Correct 0 ms 8988 KB Output is correct
23 Correct 0 ms 8988 KB Output is correct
24 Correct 0 ms 8988 KB Output is correct
25 Correct 0 ms 8988 KB Output is correct
26 Correct 0 ms 8988 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9772 KB Output is correct
2 Correct 6 ms 9772 KB Output is correct
3 Correct 3 ms 9772 KB Output is correct
4 Correct 6 ms 10164 KB Output is correct
5 Execution timed out 4000 ms 9772 KB Execution timed out
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 10152 KB Output is correct
2 Correct 209 ms 10152 KB Output is correct
3 Execution timed out 4000 ms 10300 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 13728 KB Output is correct
2 Correct 973 ms 13724 KB Output is correct
3 Execution timed out 4000 ms 13032 KB Execution timed out
4 Halted 0 ms 0 KB -