oj.uz

Submission #647165

# Submission time Handle Problem Language Result Execution time Memory
647165 2022-10-01T17:37:54 Z PoonYaPat Catfish Farm (IOI22_fish) C++17
0 / 100
 722 ms 276668 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

ll dp[300001],sl[300001],sr[300001],si[300001],mmax[100001],mmax_mi[100001],ans,ma;
map<pii,int> val;
vector<pii> vv,v,temp_val; //(index, height)
queue<pii> temp_col; //(height, index)
queue<pii> col[100001]; //(height, value)
set<int> cor_x;
queue<int> qx;
multiset<ll, greater<ll>> mo,le;

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i=0; i<m; ++i) {
        val[pii(X[i],Y[i])]=W[i];
        vv.push_back(pii(X[i],Y[i]));
        cor_x.insert(X[i]);
        if (X[i]) v.push_back(pii(X[i]-1,Y[i]));
        if (X[i]<n-1) v.push_back(pii(X[i]+1,Y[i]));
    }

    for (auto s : cor_x) qx.push(s);

    sort(vv.begin(),vv.end());
    for (auto s : vv) col[s.first].push(pii(s.second,val[pii(s.first,s.second)]));


    sort(v.begin(),v.end());

    int i=1,pre=-1;

    for (auto s : v) {
        int x=s.first, y=s.second;

        if (x==pre) { //same x_cor
            si[i]=si[i-1];
            while (!col[x].empty() & y>=col[x].front().first) {
                si[i]+=col[x].front().second;
                col[x].pop();
            }
            sr[i]=sr[i-1]+val[pii(x+1,y)];
            sl[i]=sl[i-1]+val[pii(x-1,y)];

        } else { //new x_cor
            while (!col[x].empty() & y>=col[x].front().first) {
                si[i]+=col[x].front().second;
                col[x].pop();
            }
            sr[i]=val[pii(x+1,y)];
            sl[i]=val[pii(x-1,y)];

            //clear more, less, temp
            mo.clear();
            le.clear();
            while (!temp_col.empty()) temp_col.pop();

            for (auto h : temp_val) {
                mo.insert(dp[h.first]);
                temp_col.push(pii(h.second,h.first));
            }

            temp_val.clear();

            //find max from all previous col (ma)
            while (qx.front()<x-2) {
                ma=max(ma,mmax[qx.front()]);
                qx.pop();
            }
            if (qx.front()==x-2) ma=max(ma,mmax_mi[qx.front()]);
        }

        //more to less
        while (!temp_col.empty() && temp_col.front().first<y) {
            int idx=temp_col.front().second;
            temp_col.pop();

            auto it=mo.find(dp[idx]);
            mo.erase(it);
            le.insert(dp[idx]-si[idx]-sr[idx]);
        }

        dp[i]=ma+sl[i]+sr[i];

        if (!mo.empty()) dp[i]=max(dp[i],*(mo.begin())-si[i]+sr[i]);
        if (!le.empty()) dp[i]=max(dp[i],*(le.begin())+sl[i]+sr[i]);

        mmax_mi[x]=max(mmax_mi[x],dp[i]-sr[i]);
        mmax[x]=max(mmax[x],dp[i]);

        ans=max(ans,dp[i]);
        temp_val.push_back(pii(i,y));

        ++i;
        if (x!=pre) pre=x;
    }

    return ans;
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   40 |             while (!col[x].empty() & y>=col[x].front().first) {
      |                                      ~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:48:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   48 |             while (!col[x].empty() & y>=col[x].front().first) {
      |                                      ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 86036 KB Output is correct
2 Correct 180 ms 90344 KB Output is correct
3 Correct 41 ms 67556 KB Output is correct
4 Correct 45 ms 67636 KB Output is correct
5 Runtime error 722 ms 276668 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 67608 KB Output is correct
2 Incorrect 419 ms 114700 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80957127419834'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 67532 KB Output is correct
2 Correct 40 ms 67584 KB Output is correct
3 Incorrect 147 ms 81748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '41123459278886'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 67560 KB Output is correct
2 Correct 40 ms 67668 KB Output is correct
3 Correct 43 ms 67592 KB Output is correct
4 Correct 42 ms 67584 KB Output is correct
5 Correct 37 ms 67604 KB Output is correct
6 Correct 41 ms 67668 KB Output is correct
7 Correct 41 ms 67620 KB Output is correct
8 Correct 44 ms 67644 KB Output is correct
9 Incorrect 41 ms 67748 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 67560 KB Output is correct
2 Correct 40 ms 67668 KB Output is correct
3 Correct 43 ms 67592 KB Output is correct
4 Correct 42 ms 67584 KB Output is correct
5 Correct 37 ms 67604 KB Output is correct
6 Correct 41 ms 67668 KB Output is correct
7 Correct 41 ms 67620 KB Output is correct
8 Correct 44 ms 67644 KB Output is correct
9 Incorrect 41 ms 67748 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 67560 KB Output is correct
2 Correct 40 ms 67668 KB Output is correct
3 Correct 43 ms 67592 KB Output is correct
4 Correct 42 ms 67584 KB Output is correct
5 Correct 37 ms 67604 KB Output is correct
6 Correct 41 ms 67668 KB Output is correct
7 Correct 41 ms 67620 KB Output is correct
8 Correct 44 ms 67644 KB Output is correct
9 Incorrect 41 ms 67748 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 67532 KB Output is correct
2 Correct 40 ms 67584 KB Output is correct
3 Incorrect 147 ms 81748 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '41123459278886'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 86036 KB Output is correct
2 Correct 180 ms 90344 KB Output is correct
3 Correct 41 ms 67556 KB Output is correct
4 Correct 45 ms 67636 KB Output is correct
5 Runtime error 722 ms 276668 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -