# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
369143 | 2021-02-20T14:25:27 Z | doowey | Table Tennis (info1cup20_tabletennis) | C++14 | 93 ms | 12252 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); struct item{ int val; int ii; int jj; bool operator< (const item &ff) const { return val < ff.val; } }; const int N = 150710; int dp[N]; int las[N]; vector<int> T[N]; int main(){ int n,k; cin >> n >> k; vector<int> q(n + k); for(int i = 0 ;i < n + k; i ++ ) cin >> q[i]; sort(q.begin(), q.end()); vector<item> pq; for(int i = 0 ; i < n; i ++ ){ for(int j = 1 ; j <= k + 1; j ++ ){ if(i + j < n){ pq.push_back({q[i + j] - q[i], i, i + j}); } } } sort(pq.begin(), pq.end()); vector<pii> cc; int m = n + k; int cur; int go; vector<int> sol; for(int i = 0 ;i < pq.size(); i ++ ){ cc.push_back(mp(pq[i].ii, pq[i].jj)); if(i + 1 == pq.size() || pq[i].val != pq[i + 1].val){ if(cc.size() >= n/2){ for(int i = 0 ; i < m ; i ++ ){ dp[i]=0; las[i]=-2; T[i].clear(); } for(auto x : cc){ T[x.se].push_back(x.fi); } for(int i = 0 ; i < m ; i ++ ){ dp[i]=dp[i-1]; for(auto x : T[i]){ cur = 1; if(x > 0){ cur += dp[x - 1]; } if(cur > dp[i]){ dp[i] = cur; las[i] = x-1; } } } if(dp[m - 1] >= n/2){ go = m - 1; while(go >= 0){ if(las[go] == -2){ go -- ; } else{ sol.push_back(go); sol.push_back(las[go] + 1); go = las[go]; } } sort(sol.begin(), sol.end()); for(auto x : sol) cout << q[x] << " "; cout << "\n"; return 0; } } cc.clear(); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 4204 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 15 ms | 5604 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 93 ms | 12252 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3948 KB | Output is correct |
2 | Incorrect | 3 ms | 4076 KB | Unexpected end of file - int32 expected |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 3840 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 3820 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 3820 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 3820 KB | Unexpected end of file - int32 expected |
2 | Halted | 0 ms | 0 KB | - |