oj.uz

Submission #949823

# Submission time Handle Problem Language Result Execution time Memory
949823 2024-03-19T18:18:41 Z dimashhh Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 75168 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5+ 5, MOD = 998244353;

int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
void test() {
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i] >> w[i];
        a.push_back({x[i],-y[i],i});
    }
    if(n == 1){
        cout << max(0ll,w[1]) << '\n';
        return;
    }
    sort(a.begin(),a.end());
    for(int i = 0;i < (int)a.size();i++){
        pos[a[i][2]] = i + 1;
        t[i + 1] = a[i][2];
    }
    vector<pair<long double,pair<int,int>>> cur;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            long double val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
            cur.push_back({val,{i,j}});
        }
    }
    ll res = 0;
    sort(cur.rbegin(),cur.rend());
    for(int i = 0;i < (int)cur.size();i++){
        vector<pair<int,int>> ss;
        for(int j = i;j <= (int)cur.size();j++){
            if(j == (int)cur.size() || cur[j].first != cur[i].first){
                i = j - 1;
                break;
            }
            int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
                                                                                      pos[cur[j].second.second]);
            ss.push_back({L,R});
        }
        vector<ll> sums;
        sort(ss.begin(),ss.end());
        ll mn = 0,curs = 0;
        ll max_checked;
        for(int j = 0;j < (int)ss.size();j++) {
            if (j && max_checked >= ss[j].second) continue;
            int mx = ss[j].second;
            for (int k = j; k <= (int) ss.size(); k++) {
                if (k == (int) ss.size() || ss[k].first != ss[j].first) {
                    j = k - 1;
                    break;
                }
                max_checked = ss[k].second;
                mx = ss[k].second;
            }
            int l = ss[j].first, r = mx;
            while (l < r) {
                swap(t[l], t[r]);
                pos[t[l]] = l;
                pos[t[r]] = r;
                l++;
                r--;
            }
        }
        for(int j = 1;j <= n;j++){
            curs += w[t[j]];
            res = max(res,curs - mn);
            mn = min(mn,curs);
        }
    }
    cout << res << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 8920 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 8792 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 3 ms 9052 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 3 ms 9052 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9048 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 3 ms 9052 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 3 ms 9052 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9048 KB Output is correct
33 Execution timed out 2037 ms 75168 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9052 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9048 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9048 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 1 ms 4696 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 1 ms 8540 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 1 ms 8536 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9052 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 3 ms 9052 KB Output is correct
27 Correct 3 ms 9052 KB Output is correct
28 Correct 3 ms 9052 KB Output is correct
29 Correct 3 ms 9052 KB Output is correct
30 Correct 3 ms 9052 KB Output is correct
31 Correct 3 ms 9052 KB Output is correct
32 Correct 3 ms 9048 KB Output is correct
33 Execution timed out 2037 ms 75168 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 3 ms 9052 KB Output is correct
6 Correct 2 ms 9048 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 8920 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 8792 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct
15 Correct 2 ms 8536 KB Output is correct
16 Correct 3 ms 9052 KB Output is correct
17 Correct 3 ms 9052 KB Output is correct
18 Correct 3 ms 9048 KB Output is correct
19 Correct 3 ms 9052 KB Output is correct
20 Correct 3 ms 9052 KB Output is correct
21 Correct 3 ms 9052 KB Output is correct
22 Correct 3 ms 9052 KB Output is correct
23 Correct 3 ms 9052 KB Output is correct
24 Correct 3 ms 9048 KB Output is correct
25 Correct 3 ms 9052 KB Output is correct
26 Correct 1 ms 4696 KB Output is correct
27 Correct 1 ms 4440 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 1 ms 8540 KB Output is correct
30 Correct 2 ms 8536 KB Output is correct
31 Correct 1 ms 8540 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct
33 Correct 1 ms 8540 KB Output is correct
34 Correct 2 ms 8540 KB Output is correct
35 Correct 1 ms 8536 KB Output is correct
36 Correct 3 ms 9052 KB Output is correct
37 Correct 3 ms 9052 KB Output is correct
38 Correct 3 ms 9052 KB Output is correct
39 Correct 3 ms 9052 KB Output is correct
40 Correct 3 ms 9052 KB Output is correct
41 Correct 3 ms 9052 KB Output is correct
42 Correct 3 ms 9052 KB Output is correct
43 Correct 3 ms 9052 KB Output is correct
44 Correct 3 ms 9052 KB Output is correct
45 Correct 3 ms 9052 KB Output is correct
46 Correct 3 ms 9052 KB Output is correct
47 Correct 3 ms 9048 KB Output is correct
48 Execution timed out 2037 ms 75168 KB Time limit exceeded
49 Halted 0 ms 0 KB -