# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133108 | 2019-07-20T07:34:22 Z | Mahdi_Jfri | 팀들 (IOI15_teams) | C++14 | 4000 ms | 130448 KB |
#include "teams.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 5e5 + 20; const int maxb = 20; int dp[maxn] , n , l[maxn] , r[maxn]; int seg[maxb][maxn] , lpt[maxb][maxn] , rpt[maxb][maxn]; void build(int s = 0 , int e = n , int h = 0) { if(e - s < 2) { seg[h][s] = l[s]; return; } int m = (s + e) / 2; build(s , m , h + 1); build(m , e , h + 1); int pt1 = s , pt2 = m , pt = s; while(pt != e) { if(pt2 == e || (pt1 < m && seg[h + 1][pt1] < seg[h + 1][pt2])) { lpt[h][pt] = pt1; if(pt2 == e) rpt[h][pt] = maxn; else rpt[h][pt] = pt2; seg[h][pt] = seg[h + 1][pt1++]; } else { rpt[h][pt] = pt2; if(pt1 == m) lpt[h][pt] = maxn; else lpt[h][pt] = pt1; seg[h][pt] = seg[h + 1][pt2++]; } pt++; } } inline int get(int r , int val , int s = 0 , int e = n , int h = 0) { int ans = 0; val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h]; if(val == e) return 0; while(1) { if(val >= maxn) return ans; if(e <= r) return ans + e - val; if(r <= s) return ans; int m = (s + e) / 2; if(r <= m) val = lpt[h][val] , e = m , h++; else { ans += max(0 , m - lpt[h][val]); val = rpt[h][val] , s = m , h++; } } } void init(int N, int a[], int b[]) { n = N; vector<pair<int , int> > tmp; for(int i = 0; i < n; i++) { l[i] = a[i] , r[i] = b[i]; tmp.pb({r[i] , -l[i]}); } sort(tmp.begin() , tmp.end()); for(int i = 0; i < n; i++) l[i] = -tmp[i].second , r[i] = tmp[i].first; build(); } int p[maxn] , t[maxn]; int can(int m, int k[]) { sort(k , k + m); for(int i = 0; i < m; i++) t[k[i]] = 0; int sum = 0; for(int i = 1; i <= m; i++) { p[i] = k[i - 1]; sum += p[i]; if(sum > n) return 0; t[p[i]]++; } m = unique(p + 1 , p + m + 1) - p - 1; p[0] = 0; dp[0] = 0; for(int i = 1; i <= m; i++) { dp[i] = -1e9; int x = lower_bound(r , r + n , p[i]) - r; for(int j = i - 1; j >= 0; j--) dp[i] = max(dp[i] , dp[j] + get(x , p[j] + 1)); dp[i] += t[p[i]] * p[i]; if(dp[i] + get(n , p[i] + 1) - n > 0) return 0; } return 1; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 632 KB | Output is correct |
4 | Correct | 2 ms | 508 KB | Output is correct |
5 | Correct | 2 ms | 504 KB | Output is correct |
6 | Correct | 2 ms | 504 KB | Output is correct |
7 | Correct | 2 ms | 504 KB | Output is correct |
8 | Correct | 2 ms | 632 KB | Output is correct |
9 | Correct | 2 ms | 504 KB | Output is correct |
10 | Correct | 2 ms | 504 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 636 KB | Output is correct |
13 | Correct | 2 ms | 504 KB | Output is correct |
14 | Correct | 2 ms | 504 KB | Output is correct |
15 | Correct | 2 ms | 504 KB | Output is correct |
16 | Correct | 2 ms | 504 KB | Output is correct |
17 | Correct | 2 ms | 504 KB | Output is correct |
18 | Correct | 2 ms | 504 KB | Output is correct |
19 | Correct | 2 ms | 504 KB | Output is correct |
20 | Correct | 2 ms | 504 KB | Output is correct |
21 | Correct | 2 ms | 504 KB | Output is correct |
22 | Correct | 2 ms | 504 KB | Output is correct |
23 | Correct | 2 ms | 504 KB | Output is correct |
24 | Correct | 2 ms | 504 KB | Output is correct |
25 | Correct | 2 ms | 504 KB | Output is correct |
26 | Correct | 2 ms | 504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 23532 KB | Output is correct |
2 | Correct | 48 ms | 23496 KB | Output is correct |
3 | Correct | 48 ms | 23532 KB | Output is correct |
4 | Correct | 52 ms | 23532 KB | Output is correct |
5 | Correct | 53 ms | 23532 KB | Output is correct |
6 | Correct | 41 ms | 23660 KB | Output is correct |
7 | Correct | 36 ms | 23532 KB | Output is correct |
8 | Correct | 36 ms | 23532 KB | Output is correct |
9 | Correct | 32 ms | 23660 KB | Output is correct |
10 | Correct | 32 ms | 23532 KB | Output is correct |
11 | Correct | 31 ms | 23532 KB | Output is correct |
12 | Correct | 36 ms | 23632 KB | Output is correct |
13 | Correct | 39 ms | 23532 KB | Output is correct |
14 | Correct | 39 ms | 23532 KB | Output is correct |
15 | Correct | 46 ms | 23524 KB | Output is correct |
16 | Correct | 46 ms | 23532 KB | Output is correct |
17 | Correct | 37 ms | 23504 KB | Output is correct |
18 | Correct | 37 ms | 23612 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 23532 KB | Output is correct |
2 | Correct | 55 ms | 23504 KB | Output is correct |
3 | Correct | 153 ms | 26428 KB | Output is correct |
4 | Correct | 52 ms | 23532 KB | Output is correct |
5 | Correct | 3702 ms | 23532 KB | Output is correct |
6 | Correct | 2563 ms | 23532 KB | Output is correct |
7 | Correct | 44 ms | 23504 KB | Output is correct |
8 | Correct | 1976 ms | 23532 KB | Output is correct |
9 | Correct | 32 ms | 23532 KB | Output is correct |
10 | Correct | 34 ms | 23532 KB | Output is correct |
11 | Correct | 45 ms | 23532 KB | Output is correct |
12 | Correct | 728 ms | 23532 KB | Output is correct |
13 | Correct | 271 ms | 23532 KB | Output is correct |
14 | Correct | 177 ms | 25176 KB | Output is correct |
15 | Correct | 97 ms | 23872 KB | Output is correct |
16 | Correct | 98 ms | 23788 KB | Output is correct |
17 | Correct | 125 ms | 23788 KB | Output is correct |
18 | Correct | 96 ms | 23792 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 270 ms | 125676 KB | Output is correct |
2 | Correct | 274 ms | 125732 KB | Output is correct |
3 | Correct | 587 ms | 130448 KB | Output is correct |
4 | Correct | 262 ms | 125896 KB | Output is correct |
5 | Execution timed out | 4016 ms | 125760 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |