oj.uz

Submission #852712

# Submission time Handle Problem Language Result Execution time Memory
852712 2023-09-22T14:57:39 Z abcvuitunggio Catfish Farm (IOI22_fish) C++17
3 / 100
 484 ms 187500 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define MX mx[i][idx][b]
using namespace std;
const long long INF=1e18;
vector <long long> v[100001];
vector <pair <int, long long>> s[100001],mx[100002][4][2];
int n,m;
long long x,y,res;
void update(int pos, long long val, int i, int idx){
    mx[pos][idx][0].push_back({i,val});
    mx[pos][idx][1].push_back({n-i+1,val});
}
long long get(int pos, int i, int idx, int b){
    if (b)
        pos=n-pos+1;
    int p=upper_bound(MX.begin(),MX.end(),make_pair(pos,INF))-MX.begin()-1;
    return (p<0?-INF:MX[p].second);
}
long long sum(int i, int j){
    if (i<0)
        return 0;
    return s[i][upper_bound(s[i].begin(),s[i].end(),make_pair(j,INF))-s[i].begin()-1].second;
}
long long max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W){
    n=N;
    for (int i=0;i<M;i++){
        s[X[i]].push_back({Y[i],W[i]});
        if (X[i])
            v[X[i]-1].push_back(Y[i]);
        if (X[i]<N-1)
            v[X[i]+1].push_back(Y[i]);
    }
    for (int i=0;i<n;i++){
        v[i].push_back(-1);
        sort(v[i].begin(),v[i].end());
        v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
        s[i].push_back({-1,0});
        sort(s[i].begin(),s[i].end());
        for (int j=1;j<s[i].size();j++)
            s[i][j].second+=s[i][j-1].second;
    }
    for (int i:v[n-1]){
        update(n,0,i,0);
        update(n,0,i,1);
        update(n,-sum(n-1,i),i,2);
        update(n,sum(n-2,i),i,3);
    }
    for (int i=n-1;i;i--){
        for (int j:v[i-1]){
            x=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),max(get(j,i+1,0,1),get(j,i+1,1,1)));
            y=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),get(j,i+1,3,1)-sum(i-1,j));
            update(i,x,i,0);
            update(i,y,i,1);
            update(i,x-sum(i-1,j),i,2);
            update(i,max(x,y)+sum(i-2,j),i,3);
        }
        for (int j=0;j<4;j++){
            reverse(mx[i][j][1].begin(),mx[i][j][1].end());
            for (int k=0;k<2;k++)
                for (int l=1;l<mx[i][j][k].size();l++)
                    mx[i][j][k][l].second=max(mx[i][j][k][l].second,mx[i][j][k][l-1].second);
        }
    }
    return max(get(0,1,0,1),get(0,1,1,1));
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:23: 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]
   40 |         for (int j=1;j<s[i].size();j++)
      |                      ~^~~~~~~~~~~~
fish.cpp:61:31: 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]
   61 |                 for (int l=1;l<mx[i][j][k].size();l++)
      |                              ~^~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 72636 KB Output is correct
2 Correct 143 ms 77672 KB Output is correct
3 Correct 62 ms 55124 KB Output is correct
4 Correct 65 ms 55120 KB Output is correct
5 Correct 363 ms 164596 KB Output is correct
6 Correct 484 ms 187500 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Incorrect 234 ms 103980 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479737800179'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 55104 KB Output is correct
2 Correct 62 ms 55352 KB Output is correct
3 Incorrect 114 ms 63068 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 17.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 55104 KB Output is correct
2 Correct 62 ms 55352 KB Output is correct
3 Incorrect 114 ms 63068 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 72636 KB Output is correct
2 Correct 143 ms 77672 KB Output is correct
3 Correct 62 ms 55124 KB Output is correct
4 Correct 65 ms 55120 KB Output is correct
5 Correct 363 ms 164596 KB Output is correct
6 Correct 484 ms 187500 KB Output is correct
7 Correct 5 ms 23896 KB Output is correct
8 Incorrect 234 ms 103980 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40479737800179'
9 Halted 0 ms 0 KB -