Submission #884514

#	Time	Username	Problem	Language	Result	Execution time	Memory
884514		abcvuitunggio	Teams (IOI15_teams)	C++17	0 / 100	499 ms	31696 KiB

teams

#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--)
      |                    ~~~~~~~~~^~

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