oj.uz

Submission #629884

# Submission time Handle Problem Language Result Execution time Memory
629884 2022-08-15T10:15:06 Z peti1234 Catfish Farm (IOI22_fish) C++17
0 / 100
 400 ms 477408 KB 
#include <bits/stdc++.h>

using namespace std;
const int c=3000005;
int n, m, si[c];
vector<pair<int, int> > sz[c];
vector<long long> dp0[c], dp1[c];
// 0 - megkapta a felette levoket, 1 - meg nem kapta meg

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n=N, m=M;
    for (int i=0; i<m; i++) {
        int a=X[i], b=Y[i], s=W[i];
        a++, b++;
        sz[a].push_back({b, s});
    }
    for (int i=0; i<=n+1; i++) {
        sz[i].push_back({n+1, 0});
        sort(sz[i].begin(), sz[i].end());
        si[i]=sz[i].size();
        dp0[i].resize(si[i]), dp1[i].resize(si[i]);
    }
    for (int i=1; i<=n+1; i++) {
        int x=si[i-1], y=si[i];

        // 0->1
        long long maxi=0, sum=0, pos=0;
        for (int j=0; j<x; j++) {
            maxi=max(maxi, dp0[i-1][j]);
        }
        for (int j=0; j<y; j++) {
            dp1[i][j]=maxi;
        }

        // 1->1
        maxi=0, sum=0;
        for (int j=0; j<x; j++) {
            maxi=max(maxi, dp1[i-1][j]-sum);
            sum+=sz[i][j].second;
        }
        sum=0;
        for (int j=0; j<y; j++) {
            while (pos<x && sz[i][j].first>sz[i-1][pos].first) {
                sum+=sz[i-1][pos].second;
                pos++;
            }
            dp1[i][j]=max(dp1[i][j], maxi+sum);
        }


        // 0->0
        maxi=0, sum=0, pos=0;
        for (int j=0; j<x; j++) {
            while (pos<y && sz[i-1][j].first>sz[i][pos].first) {
                sum+=sz[i][pos].second;
                pos++;
            }
            maxi=max(maxi, dp0[i-1][j]+sum);
        }
        sum=0;
        for (int j=0; j<y; j++) {
            dp0[i][j]=maxi-sum;
            sum+=sz[i][j].second;
        }


        // 1->0 olyan, csak rosszabb lehet, mint az 1->1
        for (int j=0; j<y; j++) {
            dp0[i][j]=max(dp0[i][j], dp1[i][j]);
        }
    }


    return dp0[n+1][0];
}
/*
int main()
{

    return 0;
}
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 224204 KB Output is correct
2 Correct 151 ms 226156 KB Output is correct
3 Correct 119 ms 221388 KB Output is correct
4 Correct 116 ms 221312 KB Output is correct
5 Runtime error 400 ms 477408 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 100 ms 211528 KB Output is correct
2 Incorrect 177 ms 228016 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '80901044391025'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 221420 KB Output is correct
2 Correct 120 ms 221312 KB Output is correct
3 Incorrect 140 ms 221644 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '22412430951351'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 211580 KB Output is correct
2 Correct 99 ms 211608 KB Output is correct
3 Incorrect 103 ms 211576 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 211580 KB Output is correct
2 Correct 99 ms 211608 KB Output is correct
3 Incorrect 103 ms 211576 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 211580 KB Output is correct
2 Correct 99 ms 211608 KB Output is correct
3 Incorrect 103 ms 211576 KB 1st lines differ - on the 1st token, expected: '4044', found: '6066'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 221420 KB Output is correct
2 Correct 120 ms 221312 KB Output is correct
3 Incorrect 140 ms 221644 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '22412430951351'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 224204 KB Output is correct
2 Correct 151 ms 226156 KB Output is correct
3 Correct 119 ms 221388 KB Output is correct
4 Correct 116 ms 221312 KB Output is correct
5 Runtime error 400 ms 477408 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -