oj.uz

Submission #423637

# Submission time Handle Problem Language Result Execution time Memory
423637 2021-06-11T10:43:40 Z lyc Table Tennis (info1cup20_tabletennis) C++14
24 / 100
 3000 ms 432260 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

const int mxN = 150001;
const int mxK = 401;

int N, K;
int A[mxN];
map<int,int> dpL[mxN], dpR[mxN];
map<int,int> paL[mxN], paR[mxN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> K;
    N += K;
    FOR(i,1,N){
        cin >> A[i];
    }

    if (N-K == 2) {
        cout << A[1] _ A[2] << '\n';
        return 0;
    }

    FOR(i,2,N){
        FOR(j,max(1,i-K-1),i-1){
            int diff = A[i]-A[j];
            int r = dpL[j].count(diff) ? dpL[j][diff]+1 : 2;
            if (!dpL[i].count(diff) || dpL[i][diff] < r) {
                dpL[i][diff] = r;
                paL[i][diff] = j;
            }
        }
    }

    RFOR(i,N-1,1){
        FOR(j,i+1,min(N,i+K+1)){
            int diff = A[j]-A[i];
            int r = dpR[j].count(diff) ? dpR[j][diff]+1 : 2;
            if (!dpR[i].count(diff) || dpR[i][diff] < r) {
                dpR[i][diff] = r;
                paR[i][diff] = j;
            }
        }
    }

    map<int,int> slide;
    FOR(i,1,N){
        for (auto& x : dpR[i]) {
            if (slide.count(x.first) && min(dpL[slide[x.first]][x.first], x.second)*2 >= N-K) {
                //cout << "YES" _ x.first _ slide[x.first] _ i << endl;
                int a = slide[x.first], b = i;
                vector<int> ans;
                while (SZ(ans) < (N-K)/2) ans.push_back(a), a = paL[a][x.first];
                reverse(ALL(ans));
                while (SZ(ans) < N-K) ans.push_back(b), b = paR[b][x.first];
                for (int& x : ans) {
                    cout << A[x] << ' ';
                }
                cout << endl;
                return 0;
            }
        }
        for (auto& x : dpL[i]) {
            if (!slide.count(x.first) || dpL[slide[x.first]][x.first] < x.second) {
                slide[x.first] = i;
            }
        }
    }

    assert(false);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 59104 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 36392 KB Output is correct
2 Execution timed out 3087 ms 432260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 28996 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30100 KB Output is correct
2 Correct 34 ms 31508 KB Output is correct
3 Correct 29 ms 31276 KB Output is correct
4 Correct 29 ms 31436 KB Output is correct
5 Correct 28 ms 31280 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 28492 KB Output is correct
2 Correct 17 ms 28492 KB Output is correct
3 Correct 20 ms 28464 KB Output is correct

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 57804 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 57716 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 45648 KB Output is correct
2 Runtime error 65 ms 58748 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -