This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
int n,a[500001],b[500001],cnt[200001],g[500001],l[500001],la[500001],dp[1010][1010];
void init(int N, int A[], int B[]){
sort(A,A+N);
sort(B,B+N);
n=N;
for (int i=1;i<=n;i++)
a[i]=A[i-1],b[i]=B[i-1];
for (int i=0;i<=n;i++){
g[i]=lower_bound(a+1,a+n+1,i)-a;
l[i]=upper_bound(b+1,b+n+1,i)-b-1;
la[i]=upper_bound(a+1,a+n+1,i)-a-1;
}
}
int countbetween(int i, int j){
return max(l[j]-g[i]+1,0);
}
int cost(int i, int j){
return max(la[j]-g[i]+1,0)-countbetween(i,j-1);
}
int can(int M, int K[]){
int sum=0;
for (int i=0;i<M;i++){
sum+=K[i];
if (sum>n)
return 0;
}
vector <int> ve;
for (int i=0;i<M;i++){
cnt[K[i]]++;
if (cnt[K[i]]==1)
ve.push_back(K[i]);
}
ve.push_back(0);
sort(ve.begin(),ve.end());
int mx=0;
for (int i=ve.size()-1;i>=0;i--)
for (int j=ve.size()-1;j>i;j--){
dp[i][j]=max(dp[i][j+1],dp[j][j+1]+ve[j]*cnt[ve[j]]-cost(ve[i]+1,ve[j]));
if (!i)
mx=max(mx,dp[i][j]);
}
for (int i=ve.size()-1;i>=0;i--)
for (int j=ve.size()-1;j>i;j--)
dp[i][j]=0;
for (int i=0;i<M;i++)
cnt[K[i]]=0;
return (!mx);
}
Compilation message (stderr)
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:12:38: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
12 | g[i]=lower_bound(a+1,a+n+1,i)-a;
| ~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:13:40: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
13 | l[i]=upper_bound(b+1,b+n+1,i)-b-1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:14:41: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
14 | la[i]=upper_bound(a+1,a+n+1,i)-a-1;
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:39:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
39 | for (int i=ve.size()-1;i>=0;i--)
| ~~~~~~~~~^~
teams.cpp:40:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
40 | for (int j=ve.size()-1;j>i;j--){
| ~~~~~~~~~^~
teams.cpp:45:25: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
45 | for (int i=ve.size()-1;i>=0;i--)
| ~~~~~~~~~^~
teams.cpp:46:29: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
46 | for (int j=ve.size()-1;j>i;j--)
| ~~~~~~~~~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |