# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
21794 | 2017-04-25T20:48:12 Z | sbansalcs | Teams (IOI15_teams) | C++14 | 4000 ms | 13744 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9004 KB | Output is correct |
2 | Correct | 0 ms | 9004 KB | Output is correct |
3 | Correct | 0 ms | 9004 KB | Output is correct |
4 | Correct | 0 ms | 9004 KB | Output is correct |
5 | Correct | 0 ms | 9004 KB | Output is correct |
6 | Correct | 0 ms | 9004 KB | Output is correct |
7 | Correct | 0 ms | 9004 KB | Output is correct |
8 | Correct | 0 ms | 9004 KB | Output is correct |
9 | Correct | 0 ms | 9004 KB | Output is correct |
10 | Correct | 0 ms | 9004 KB | Output is correct |
11 | Correct | 0 ms | 9004 KB | Output is correct |
12 | Correct | 0 ms | 9004 KB | Output is correct |
13 | Correct | 0 ms | 9004 KB | Output is correct |
14 | Correct | 0 ms | 9004 KB | Output is correct |
15 | Correct | 0 ms | 9004 KB | Output is correct |
16 | Correct | 0 ms | 9004 KB | Output is correct |
17 | Correct | 0 ms | 9004 KB | Output is correct |
18 | Correct | 0 ms | 9004 KB | Output is correct |
19 | Correct | 0 ms | 9004 KB | Output is correct |
20 | Correct | 0 ms | 9004 KB | Output is correct |
21 | Correct | 0 ms | 9004 KB | Output is correct |
22 | Correct | 0 ms | 9004 KB | Output is correct |
23 | Correct | 0 ms | 9004 KB | Output is correct |
24 | Correct | 0 ms | 9004 KB | Output is correct |
25 | Correct | 0 ms | 9004 KB | Output is correct |
26 | Correct | 0 ms | 9004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 9788 KB | Output is correct |
2 | Correct | 3 ms | 9788 KB | Output is correct |
3 | Correct | 6 ms | 9788 KB | Output is correct |
4 | Correct | 9 ms | 10180 KB | Output is correct |
5 | Execution timed out | 4000 ms | 9788 KB | Execution timed out |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 143 ms | 10168 KB | Output is correct |
2 | Correct | 263 ms | 10168 KB | Output is correct |
3 | Execution timed out | 4000 ms | 10316 KB | Execution timed out |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 983 ms | 13744 KB | Output is correct |
2 | Correct | 946 ms | 13740 KB | Output is correct |
3 | Execution timed out | 4000 ms | 13048 KB | Execution timed out |
4 | Halted | 0 ms | 0 KB | - |