oj.uz

Submission #627709

# Submission time Handle Problem Language Result Execution time Memory
627709 2022-08-12T19:26:19 Z Yomapeed Catfish Farm (IOI22_fish) C++17
9 / 100
 1000 ms 65948 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]);
            }
        }
        
        swap(L, nL);
        swap(R, nR);
        swap(S, nS);
        // 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 1100 ms 59936 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 212 KB Output is correct
2 Execution timed out 1086 ms 65948 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 15136 KB Output is correct
2 Correct 54 ms 8840 KB Output is correct
3 Correct 122 ms 16656 KB Output is correct
4 Correct 122 ms 17244 KB Output is correct
5 Correct 173 ms 20656 KB Output is correct
6 Correct 164 ms 20684 KB Output is correct
7 Correct 169 ms 20548 KB Output is correct
8 Correct 170 ms 20620 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56804606856'
14 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56804606856'
14 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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '56941582046', found: '56804606856'
14 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 15136 KB Output is correct
2 Correct 54 ms 8840 KB Output is correct
3 Correct 122 ms 16656 KB Output is correct
4 Correct 122 ms 17244 KB Output is correct
5 Correct 173 ms 20656 KB Output is correct
6 Correct 164 ms 20684 KB Output is correct
7 Correct 169 ms 20548 KB Output is correct
8 Correct 170 ms 20620 KB Output is correct
9 Execution timed out 1086 ms 55688 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

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