oj.uz

Submission #555235

# Submission time Handle Problem Language Result Execution time Memory
555235 2022-04-30T09:57:11 Z tht2005 Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 2000 ms 11392 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

struct dt {
    LL n, d;
    int i;
    bool t;
    bool operator< (const dt& B) const {
        return n * B.d > B.n * d;
    }
};

const int N = 100005;
int n, m, cnt, a[N], b[N], x[N], y[N];
LL res;
multiset<dt> S;
multiset<dt>::iterator z[N], t[N];
set<int> c, d;

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) {
        scanf("%d", a + i);
    }
    for(int i = 0; i < m; ++i) {
        scanf("%d", b + i);
    }
    for(int i = 1; i < n; ++i) {
        z[i] = S.insert({ a[i] - a[i - 1], 1, i, 0 });
        c.insert(i);
    }
    for(int i = 1; i < m; ++i) {
        t[i] = S.insert({ b[i] - b[i - 1], 1, i, 1 });
        d.insert(i);
    }
    while(!S.empty()) {
        auto [nn, dd, i, _] = *S.begin();
        S.erase(S.begin());
        if(_) {
            auto it = d.erase(d.find(i));
            if(it != d.end()) {
                int j = *it;
                dt tmp = *t[j];
                S.erase(t[j]);
                tmp.n += nn;
                tmp.d += dd;
                t[j] = S.insert(tmp);
            }
            y[i] = cnt++;
        }
        else {
            auto it = c.erase(c.find(i));
            if(it != c.end()) {
                int j = *it;
                dt tmp = *z[j];
                S.erase(z[j]);
                tmp.n += nn;
                tmp.d += dd;
                z[j] = S.insert(tmp);
            }
            x[i] = cnt++;
        }
    }
    res = 0;
    for(int i = n - 1, j = m - 1; i || j; ) {
        if(j == 0 || x[i] < y[j]) {
            res += b[j];
            --i;
        }
        else {
            res += a[i];
            --j;
        }
    }
    printf("%lld", res);
    return 0;
}

Compilation message

kyoto.cpp: In function 'int main()':
kyoto.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
kyoto.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%d", a + i);
      |         ~~~~~^~~~~~~~~~~~~
kyoto.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", b + i);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Execution timed out 2080 ms 1876 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 2004 KB Output is correct
4 Execution timed out 2075 ms 11392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Execution timed out 2080 ms 1876 KB Time limit exceeded
4 Halted 0 ms 0 KB -