oj.uz

Submission #834431

# Submission time Handle Problem Language Result Execution time Memory
834431 2023-08-22T14:13:26 Z gagik_2007 Catfish Farm (IOI22_fish) C++17
23 / 100
 1000 ms 40016 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define ff first
#define ss second
 
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=100007;
ll n,m,k;
ll pf[N][5]; // minchev j-rdy gumary
ll dp[N][5][5];
vector<pair<int,ll>>g[N];

int vorna_ste(int col, int row){
    if(col<0||col>=n)return 0;
    for(int i=0;i<g[col].size();i++){
        if(g[col][i].ff>row){
            return i;
        }
    }
    return g[col].size();
}

ll max_weights(int NN, int MM, vector<int> X, vector<int> Y, vector<int> W) {
    n=NN;
    m=MM;
    for(int i=0;i<m;i++){
        g[X[i]].push_back({Y[i]+1,W[i]});
        // assert(X[i]==Y[i]);
    }
    for(int i=0;i<n;i++){
        g[i].push_back({n+1,0});
        sort(g[i].begin(),g[i].end());
        for(int j=0;j<g[i].size();j++){
            pf[i][j+1]=g[i][j].ss;
            pf[i][j+1]+=pf[i][j];
        }
    }
    for(int i=0;i<g[0].size();i++){
        // cout<<dp[0][1][1]<<endl;
        dp[0][0][i]=pf[1][vorna_ste(1,g[0][i].ff-1)];
        // cout<<"0, 0, "<<i<<": "<<dp[0][0][i]<<endl;
    }
    ll ans=0;
    for(int i=1;i<n;i++){
        for(int j=0;j<g[i].size();j++){
            for(int k=0;k<g[i-1].size();k++){
                // cout<<i<<", "<<k<<", "<<j<<": ";
                for(int p=0;p<(i-2>=0?g[i-2].size():1);p++){
                    ll res=dp[i-1][p][k];
                    res-=pf[i][vorna_ste(i,min(g[i-1][k].ff,g[i][j].ff)-1)];
                    if(g[i][j].ff>(i-2>=0?g[i-2][p].ff:0)&&g[i][j].ff>g[i-1][k].ff){
                        res+=pf[i-1][vorna_ste(i-1,g[i][j].ff-1)]
                            -pf[i-1][vorna_ste(i-1,
                            max((i-2>=0?g[i-2][p].ff:0),g[i-1][k].ff)-1)];
                        // cout<<vorna_ste(i-1,g[i][j].ff-1)<<"  ";
                    }
                    if(i!=n-1){
                        res+=pf[i+1][vorna_ste(i+1,g[i][j].ff-1)];
                    }
                    dp[i][k][j]=max(dp[i][k][j],res);
                    // cout<<res<<" ";
                }
                ans=max(ans,dp[i][k][j]);
                // cout<<dp[i][k][j]<<"\n";
            }
        }
    }
    return ans;
}

Compilation message

fish.cpp: In function 'int vorna_ste(int, int)':
fish.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<g[col].size();i++){
      |                 ~^~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int j=0;j<g[i].size();j++){
      |                     ~^~~~~~~~~~~~
fish.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<g[0].size();i++){
      |                 ~^~~~~~~~~~~~
fish.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<g[i].size();j++){
      |                     ~^~~~~~~~~~~~
fish.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int k=0;k<g[i-1].size();k++){
      |                         ~^~~~~~~~~~~~~~
fish.cpp:57:30: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   57 |                 for(int p=0;p<(i-2>=0?g[i-2].size():1);p++){
      |                             ~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29232 KB Output is correct
2 Correct 19 ms 29268 KB Output is correct
3 Correct 37 ms 29008 KB Output is correct
4 Correct 33 ms 30796 KB Output is correct
5 Correct 60 ms 34200 KB Output is correct
6 Correct 55 ms 34124 KB Output is correct
7 Correct 58 ms 34136 KB Output is correct
8 Correct 63 ms 34252 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '526641859880'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '526641859880'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Incorrect 2 ms 2644 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '526641859880'
10 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29232 KB Output is correct
2 Correct 19 ms 29268 KB Output is correct
3 Correct 37 ms 29008 KB Output is correct
4 Correct 33 ms 30796 KB Output is correct
5 Correct 60 ms 34200 KB Output is correct
6 Correct 55 ms 34124 KB Output is correct
7 Correct 58 ms 34136 KB Output is correct
8 Correct 63 ms 34252 KB Output is correct
9 Correct 59 ms 34124 KB Output is correct
10 Correct 54 ms 21352 KB Output is correct
11 Correct 122 ms 39936 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Correct 1 ms 2644 KB Output is correct
15 Correct 1 ms 2644 KB Output is correct
16 Correct 1 ms 2644 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Correct 27 ms 29132 KB Output is correct
19 Correct 20 ms 29236 KB Output is correct
20 Correct 19 ms 29192 KB Output is correct
21 Correct 19 ms 29140 KB Output is correct
22 Correct 63 ms 33852 KB Output is correct
23 Correct 108 ms 40016 KB Output is correct
24 Correct 111 ms 39960 KB Output is correct

Subtask #8
0 / 16.0

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