oj.uz

Submission #627708

# Submission time Handle Problem Language Result Execution time Memory
627708 2022-08-12T19:24:31 Z Yomapeed Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 76968 KB 
#include "fish.h"

#include<bits/stdc++.h>
#define pi 3.141592653589793238
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second 
#define printclock cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll B) { return (unsigned ll)rng() % B;}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void chmax(ll &a, ll b){
    a = max(a, b);
}
long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    
    vector<vector<int>> adj(n);
    for(int i = 0; i < m; i++){
        adj[x[i]].pb(y[i]);
    }
    
    map<pair<int, int>, ll> score;
    for(int i = 0; i < m; i++){
        score[{x[i], y[i]}] = w[i];
    }
    map<ll, ll> L, R, S;
    L[-1] = R[-1] = 0;
    S[-1] = 0;
    for(int i = 0; i < n; i++){
        set<int> nys, nyx;
        nys.insert(-1);
        for(auto u : adj[i]){
            nys.insert(u);
        }
        nyx = nys;
        if(i) {
            for(auto [a, b] : L){
                nys.insert(a);
            }
            for(auto u : adj[i - 1]){
                nyx.insert(u);
            }
        }    
        if(i + 1 < n){
            for(auto u : adj[i + 1]){
                nys.insert(u);
                nyx.insert(u);
            }

        }
        vector<int> ny;
        for(auto u : nys) ny.pb(u);
        map<ll, ll> nL, nR, nS;
        for(auto u : ny){
            nS[u] += score[{i, u}];
        }
        int p = -1;
        for(auto [a, b] : nS){
            if(p != -1){
                nS[a] += nS[p];
            }
            p = a;
        }
        
        {
            //Case 1.1
            ll mx = -INF;
            for(auto j : ny){
                if(i){
                    chmax(mx, L[j]);
                }
                chmax(nL[j], mx);
            }
        }
        {
            //Case 1.2
            ll mx = -INF;
            for(int k = ny.size() - 1; k >= 0; k--){
                int j = ny[k];
                chmax(nL[j], mx - nS[j]);
                if(i){
                    chmax(mx, L[j] + nS[j]);
                }
            }
        }
        {
            //Case 2.1
            ll mx = -INF;
            for(auto j : ny){
                if(i){
                    chmax(mx, R[j] - S[j]);
                }
                chmax(nL[j], mx + S[j]);
            }

        }
        {
            //Case 2.2
            ll mx = -INF;
            for(int k = ny.size() - 1; k >= 0; k--){
                int j = ny[k];
                chmax(nL[j], mx - nS[j]);
                if(i){
                    chmax(mx, R[j] + nS[j]);
                }
            }
        }
        {
            //Case 3.1
            ll mx = -INF;
            for(auto j : ny){               
                chmax(mx, L[j]);
            }
            for(auto j : ny){               
                chmax(nR[j], mx);
            }
        }
        {
            //Case 4.1
            ll mx = -INF;
            for(auto j : ny){
                chmax(mx, R[j] - S[j]);
                chmax(nR[j], mx + S[j]);
            }

        }
        {
            //Case 4.2
            ll mx = -INF;
            for(int k = ny.size() - 1; k >= 0; k--){
                int j = ny[k];
                chmax(nR[j], mx);
                chmax(mx, R[j]);
            }
        }
        map<ll,ll> nnL, nnR, nnS;
        for(auto u : nyx){
            nnL[u] = nL[u];
            nnR[u] = nR[u];
            nnS[u] = nS[u];
        }
        swap(L, nnL);
        swap(R, nnR);
        swap(S, nnS);
        // cout << i << " $$$$$$$$$$$$$$$$$$$$$" << endl;
        // for(auto [a, b] : L){
        //     cout << a << " : " << b << " " << R[a] << endl;
        // }
    }
    ll ans = 0;
    for(auto [a, b] : L){
        chmax(ans, b);
        // cout << a << " : " << b << endl;
        chmax(ans, R[a]);
    }
    return ans;
}

Compilation message

fish.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("O3")
      | 
fish.cpp:8: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    8 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8880 KB Output is correct
2 Correct 64 ms 8860 KB Output is correct
3 Correct 129 ms 14756 KB Output is correct
4 Correct 157 ms 13928 KB Output is correct
5 Correct 190 ms 20636 KB Output is correct
6 Correct 199 ms 21548 KB Output is correct
7 Correct 216 ms 22164 KB Output is correct
8 Correct 198 ms 22208 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Incorrect 5 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448623543144'
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Incorrect 5 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448623543144'
13 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Incorrect 5 ms 468 KB 1st lines differ - on the 1st token, expected: '450122905247', found: '448623543144'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8880 KB Output is correct
2 Correct 64 ms 8860 KB Output is correct
3 Correct 129 ms 14756 KB Output is correct
4 Correct 157 ms 13928 KB Output is correct
5 Correct 190 ms 20636 KB Output is correct
6 Correct 199 ms 21548 KB Output is correct
7 Correct 216 ms 22164 KB Output is correct
8 Correct 198 ms 22208 KB Output is correct
9 Correct 435 ms 40324 KB Output is correct
10 Correct 198 ms 15896 KB Output is correct
11 Correct 394 ms 30292 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 224 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 63 ms 8880 KB Output is correct
19 Correct 66 ms 8932 KB Output is correct
20 Correct 63 ms 8892 KB Output is correct
21 Correct 70 ms 8852 KB Output is correct
22 Incorrect 590 ms 38444 KB 1st lines differ - on the 1st token, expected: '45561826463480', found: '45004839293209'
23 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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