Submission #419727

#TimeUsernameProblemLanguageResultExecution timeMemory
419727PbezzTeams (IOI15_teams)C++14
0 / 100
53 ms16212 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back typedef pair<ll,ll> pii; const ll MAXN = 5e5+5; const ll INF = 1e15+7; int presum[MAXN]; //presum[i] = quantos podem equipa de i int started[MAXN]; //started[i] = quantos A[j]<=i void init(int N, int A[], int B[]) { ll i; for(i=0;i<N;i++){ presum[A[i]]++; presum[B[i]+1]--; started[A[i]]++; } presum[0]=0; started[0]=0; for(i=1;i<=N+20;i++){ presum[i]+=presum[i-1]; started[i]+=started[i-1]; } } int can(int M, int K[]) { sort(K,K+M); int i,j,cur,x; int dp[M+1]; dp[0]=0; for(i=1;i<=M;i++){ dp[i] = dp[i-1] + K[i-1]; } //dp[i] e a soma dos primeiros i valores de k for(i=0;i<M;i++){ for(j=i;j<M;j++){ cur = dp[j+1]-dp[i]; //ver se ha pelo menos cur pessoas neste intervalo //somar os que começaram aqui com os que ja vieram x = presum[K[i]]; x += ( started[K[j]] - started[K[i]] ); if(x<cur)return 0; } } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...